欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法之素数筛法

程序员文章站 2024-03-08 23:10:46
...

<1>方法一

算法之素数筛法

算法之素数筛法

//判断是否是一个素数
int IsPrime(int a){
    //0,1,负数都是非素数
    if(a <= 1){
        return 0;
    }
    //计算枚举上界,为防止double值带来的精度损失,所以采用根号值取整后再加1,即宁愿多枚举一个,也不愿少枚举一个数
    int bound = (int)sqrt(a) + 1;
    for(int i = 2;i < bound;i++){
        //依次枚举这些数能否整除x,若能则必不是素数
        if(a % i == 0){
            return 0;
        }
    }
    return 1;
}



算法之素数筛法

 

<2>方法二

算法之素数筛法

 

#define MAXSIZE 10001
 
int Mark[MAXSIZE];
int prime[MAXSIZE];
 
//判断是否是一个素数  Mark 标记数组 index 素数个数
int Prime(){
	int index = 0;
	memset(Mark,0,sizeof(Mark));
	for(int i = 0;i < MAXSIZE;i++){
		//已被标记
		if(Mark[i] == 1){
			continue;
		}
		else{
			//否则得到一个素数
			prime[index++] = i;
			//标记该素数的倍数为非素数
			for(int j = i*i;j < MAXSIZE;j += i){
				Mark[j] = 1;
			}
		}
	}
	return index;
}

<3>方法三

这种方法比较好理解,初始时,假设全部都是素数,当找到一个素数时,显然这个素数乘上另外一个数之后都是合数

把这些合数都筛掉,即算法名字的由来。但仔细分析能发现,这种方法会造成重复筛除合数,影响效率。

比如30,在i=2的时候,k=2*15筛了一次;在i=5,k=5*6 的时候又筛了一次。所以,也就有了快速线性筛法。

int Mark[MAXSIZE];
int prime[MAXSIZE];
 
//判断是否是一个素数  Mark 标记数组 index 素数个数
int Prime(){
    int index = 0;
    memset(Mark,0,sizeof(Mark));
    for(int i = 2; i < MAXSIZE; i++)
    {
        //如果未标记则得到一个素数
        if(Mark[i] == 0){
            prime[index++] = i;
        }
        //标记目前得到的素数的i倍为非素数
        for(int j = 0; j < index && prime[j] * i < MAXSIZE; j++)
        {
            Mark[i * prime[j]] = 1;
            if(i % prime[j] == 0){
                break;
            }
        }
    }
    return index;
}

利用了每个合数必有一个最小素因子。每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。
代码中体现在:
if(i%prime[j]==0)break;
prime数组 中的素数是递增的,当 i 能整除 prime[j],那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。
因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。
在满足i%prme[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。

 

参考博文:点击打开链接

习题练习:点击打开链接

相关标签: 筛法