求前N个质数

时间：2021-07-29 10:57:19

入门级的标准解法如下：

#include <iostream>
#include <vector>

using namespace std;

vector<int> ivec;

bool isPrime(int number)
{
	bool result = true;

	for (int i = 2; i < number; i++)
	{
		if (number % i == 0)
		{
			result = false;
			break;
		}		
	}

	return result;
}

void generateNPrime(int N)
{
	int count = N;

	int number = 2;
	while (count)
	{
		if (isPrime(number) == true)
		{
			count--;
			ivec.push_back(number);
		}
		number++;
	}
}

void main()
{
	generateNPrime(100);
	copy(ivec.begin(), ivec.end(), ostream_iterator<int>(cout, " "));
}


有两个小小的改进地方就是对于for循环的判断上 

bool isPrime(int number)
{
	bool result = true;

	for (int i = 2; i <= number >> 1; i++)
	{
		if (number % i == 0)
		{
			result = false;
			break;
		}		
	}

	return result;
}

bool isPrime(int number)
{
	bool result = true;

	for (int i = 2; i <= sqrt((double)(number)); i++)
	{
		if (number % i == 0)
		{
			result = false;
			break;
		}		
	}

	return result;
}

比起开方运算，更建议使用平方来求解，平方的效率更高，而且开方存在精度问题

bool isPrime(int number)
{
	bool result = true;

	for (int i = 2; i * i <= number; i++)
	{
		if (number % i == 0)
		{
			result = false;
			break;
		}		
	}

	return result;
}

先来看一下100以内的素数：

2 3 5 7 11 13 17...

我们可以看到素数的规律在5之后是2、4、2、4这样间隔着出现，但是会一直这样间隔出现吗，答案是否定的，但是非这样的间隔必然不是素数

因为6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5，只有6n+1和6n+5需要检测是否为素数

所以可以做一定程度上的筛选：

void generateNPrime(int N)
{
	int count = N;

	int number = 5;
	ivec.push_back(2);
	ivec.push_back(3);
	ivec.push_back(5);
	count -= 3;
	int gap = 2;
	while (count)
	{
		number += gap;
		gap = 6 - gap;
		if (isPrime(number) == true)
		{
			count--;
			ivec.push_back(number);
		}
	}
}

时间复杂度为O(N)的素数筛选法！！！

原理如下：

1. 首选选取一个素数n

2. 选取素数m，m从n开始，依次选取下一个素数，跳出条件是n * m <= N

3. 选取素数p，p从m * n开始选取，每次*素数n，跳出条件是p * n <= N

删除

例如20以内的素数

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,16, 17, 18, 19, 20

选取素数n，n = 2; 那么m = 2, p = 4;

开始remove p，循环下来，4, 8, 16全部被删除

m选取下一个数，选取3

remove p，循环下来，6, 12

m选取下一个数，选取5

remove p，循环下来，删除10, 20

m选取下一个数，选取7，删除14

m选取下一个数，选取9，删除18

第一重循环跳出，经过本轮筛选，剩下的数字为：

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,16, 17, 18, 19, 20

重复上面的逻辑，再经过一轮筛选，不难得出剩下的数字为：

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,15,16, 17, 18, 19, 20

两轮筛选后，循环跳出~

#include <iostream>

using namespace std;

#define MAXSIZE 1000
#define NEXT(x) x = next[x]
#define PREVIOUS(x) x = previous[x - 1]
#define  REMOVE(x) { next[PREVIOUS(x)] = next[x]; \
                      previous[next[x]] = previous[x]; }
#define INITIAL(n) { unsigned long i; \
						for (int i = 2; i <= n; i++) \
							previous[i] = i - 1, next[i] = i + 1; \
						previous[2] = next[n] = 0; \
					}

void main()
{
	unsigned long previous[MAXSIZE + 1];
	unsigned long next[MAXSIZE + 1];
	unsigned long prime, fact, i, mult;
	unsigned long n;
	unsigned long count = 0;
	printf("\nLinear Sieve Program");
	printf("\n====================");
	printf("\n\nPrime Numbers between 2 to --> ");
	scanf("%d", &n);
	INITIAL(n);
	for (prime = 2; prime * prime <= n; prime = next[prime])
		for (fact = prime; prime * fact <= n; fact = next[fact])
			for (mult = prime * fact; mult <= n; mult *= prime)
			{
				if (fact == 9)
					cout << "mult = " << mult << endl;
				next[previous[mult]] = next[mult];
				previous[next[mult]] = previous[mult]; 
			}

	for (int i = 2; i != 0; i = next[i])
	{
		if (count % 8 == 0)
			printf("\n");
		printf("%6ld", i);
		count++;
	}

	printf("\n\nThere are %ld Prime Numbers in Total", count);
}



标签：

相关文章