必威体育Betway必威体育官网
当前位置:首页 > IT技术

求素数及素数表的获取

时间:2019-09-06 06:11:04来源:IT技术作者:seo实验室小编阅读:57次「手机版」
 

素数表

质数(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;
}

相关阅读

分享到:

栏目导航

推荐阅读

热门阅读