求素数

下面以求1000000以内的素数为例，介绍几种求素数的方法。int prime[N]为所求结果存放的数组。

 

1. 根据概念求解

 

void makePrime(){
	int i,j,k=0;
	bool flag = true;
	for(i=2;i<N;i++){
		for(j=2;j<=i;j++){
			if(i%j == 0){
				flag = false;
				break;
			}
		}
		if(flag){
			prime[k++] = i;
		}
		flag = true;
	}
}

2. 在（1）的基础上缩小范围

    根据定理：如果n不是素数, 则n有满足1<d<=sqrt(n)的一个因子d

 

void makePrime(){
	int i,j,k=0;
	bool flag = true;
	for(i=2;i<N;i++){
		for(j=2;j<=sqrt(i);j++){
			if(i%j == 0){
				flag = false;
				break;
			}
		}
		if(flag){
			prime[k++] = i;
		}
		flag = true;
	}
}

3. 在（2）的基础上除去偶数 

 

void makePrime(){
	int i,j,k=1;
        prime[0] = 2;
	bool flag = true;
	for(i=3;i<N;i++){
		for(j=3;j<=sqrt(i);j+=2){
			if(i%j == 0){
				flag = false;
				break;
			}
		}
		if(flag){
			prime[k++] = i;
		}
		flag = true;
	}
}

4. 用6N±1法求素数

 

    任何一个自然数，总可以表示成为如下的形式之一：

       6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)

    显然，当N≥1时，6N，6N+2，6N+3，6N+4都不是素数，只有形如6N+1和6N+5的自然数有可能是素数。所以，除了2和3之外，所有的素数都可以表示成6N±1的形式(N为自然数)。

根据上述分析，我们可以构造另一面筛子，只对形如6 N±1的自然数进行筛选，这样就可以大大减少筛选的次数，从而进一步提高程序的运行效率和速度。

    例如在（3）的基础上改进算法：

 

void makePrimes2(){
	int i,j,k=1;
    prime[0] = 2;
	bool flag = true;
	for(i=3;i<N;i++){
		if((i+1)%6 == 0 || (i-1)%6 == 0){
			for(j=3;j<=sqrt(i);j+=2){
				if(i%j == 0){
					flag = false;
					break;
				}
			}
			if(flag){
				prime[k++] = i;
			}
			flag = true;
		}
	}
}

  5.厄拉多塞筛法求素数

 

    简单介绍一下厄拉多塞筛法。厄拉多塞是一位古希腊数学家，他在寻找素数时，采用了一种与众不同的方法：先将2~N的各数写在纸上。在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 N的素数。

    这很像一面筛子，把满足条件的数留下来，把不满足条件的数筛掉。

 

void makePrimes(){
        bool flag[N];     //额外申请的空间用于标记素数，false为素数，true为非素数
	int i,j,num = 0;
	flag[2] = flag[3] = false;
	for(i = 2; i < N; ++i){
		if(!flag[i])
			prime[num++] = i;
		for(j=0; (j<num && i*prime[j] < N);j++){
			flag[i*prime[j]] = true;
		}
	}
}

 这种方法在时间上比上几种求法都高效，不过需要额外申请空间。