素埃里克森筛法

全栈程序员站长

发布于 2022-07-14 18:22:23

1840

发布于 2022-07-14 18:22:23

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是全栈君

原则：

第一2~n的记录数。2作为最小质数。所以2多个不是素数，从记录介质划掉，扫描后再次。将3作为最小质数。3倍数划掉，如此下去，求出全部素数。

如表格所看到的：

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

代码：

推断是否是素数：

bool is_prime(int n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0)
            return false;
    }
    return n!=1;
}

埃氏筛法：

const int MAX  = 1000;
int prime[MAX];
bool is_prime[MAX];

int sieve(int n){
    int p=0;
    for(int i=0;i<=n;i++)
        is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for(int i=2;i<=n;i++){
        if(is_prime[i]){
            prime[p++] = i;
            for(int j=2*i;j<=n;j+=i)  is_prime[j] = false;
        }
    }
    return p;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/117863.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021年12月，如有侵权请联系 cloudcommunity@tencent.com 删除

https