求素数及素数表的获取

　

素数表

质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数；否则称为合数。

最小的质数是2。

1.素数的判断

由于一些题目中素数的判断只是其中的一部分，所以如果这个时候的时间复杂度为O(n)实际上有点大了，所以我们需要更加快速的判定方法。注意到如果在2~n-1中存在n的约数，不妨设为k，即n%k == 0，那么由k * (n/k) ==n可知，n/k也是n的一个约数,且k与n/k中一定满足其中一个小于sqrt(n)另一个大于sqrt(n)，其中sqrt(n)为根号n。

所以，我们只需要判定n能否被2,3,……sqrt(n)中的一个整除，即可判定n是否为素数，其算法的时间复杂度为O(sqrt(n)).

代码如下：

bool isPrime(int n){
	if(n <= 1) return false;
	int aqr = (int)sqrt(1.0*n);
	for(int i = 2; i <= sqr; i++)
	{
		if（n % i == 0) return false;
	}
	return true;
}

上述代码中，sqrt的作用是为一个浮点数开根号，需要添加math.h头文件。

由于sqrt的参数要求是浮点数，因此在n前面需要乘上1.0使其变成浮点型。

2.素数表的获取

用以上的方法实现素数的判断后，时间复杂度为O(sqrt(n) )，现在要把这些素数都加到素数表中就很容易了，直接采用枚举的方法即可，而枚举部分的复杂度为O(n)，所以总复杂度为O(n*sqrt(n))。这个复杂度对n不超过十的五次方的大小是没有问题的，考试时大部分涉及素数表的题目都不会超过这个范围，代码如下：

const int maxn = 101;  
int prime[maxn], pNum = 0;
bool p[maxn] = {0};
void Find_Prime() {
	for(int i = 1; i < maxn; i++)
	{
		if(isPrime(i) == true){
			prime[pNum++] = i;
			p[i] = true;
		}
	}
}

上面算法在n到十的五次方以内都是可以承受的，如果出现大范围素数表需要求解，以上解法将力不从心，所以可以使用各种“筛法”，其中“埃式筛法”是最简单的一种。

其实“埃式筛法”就是如果我发现了某一个数是一个素数，那么这个数的所有倍数，都不是素数了，就把这些倍数全部筛掉了。

A[i] = i;
for(int k = 2; k < maxn; k++)
{
	if(A[k]!= -1)
		for(j = 2; j*k<n; j++)
			A[j*k] = -1;
}

下面为一个具体的例子：

给定两个数，求两个数之前的所有素数。

#include <stdio.h>
const int maxn = 1000001;
int prime[maxn], num = 0;
bool p[maxn] = {0};
void Find_Prime (int n) {
    for(int i = 2; i < maxn; i++) {
        if(p[i] == false) {
            prime[num++] = i;
            // 只需要n个素数，因此超时即可结束
            if(num >= n) break;
            for(int j = i + i; j < maxn; j +=i) {
                p[j] = true;// 都不是素数
            }
        }
    }
}

int main() {
    int m, n, count = 0;
    scanf("%d%d", &m, &n);
    Find_Prime(n);
    // 输出从第m个素数至第n个素数
    for(int i = m; i <= n; i++) {
        // 下标从0开始
        printf("%d",prime[i - 1]);
        count++;
        if(count % 10 != 0 && i < n) printf(" ");
        else printf("\n");
    }
    return 0;
}

相关阅读