埃拉托斯特尼筛法

编辑:裨益网互动百科 时间:2019-12-11 03:44:43
编辑 锁定
同义词 埃氏筛一般指埃拉托斯特尼筛法
埃拉托斯特尼筛法,简称埃氏筛或爱氏筛,是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。
中文名
埃拉托斯特尼筛法
外文名
sieve of Eratosthenes
别    称
筛法
提出者
古希腊数学家埃拉托斯特尼所
提出时间
公元前250
应用学科
数学
适用领域范围
数论

埃拉托斯特尼筛法算式

编辑
要得到自然数n以内的全部素数,必须把不大于
的所有素数的倍数剔除,剩下的就是素数。
给出要筛数值的范围n,找出以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去......。
步骤
详细列出算法如下:
  1. 列出2以后的所有序列:
    • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  2. 标出序列中的第一个素数,也就是2,序列变成:
    • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  3. 将剩下序列中,划掉2的倍数,序列变成:
    • 2 3 5 7 9 11 13 15 17 19 21 23 25
  4. 如果现在这个序列中最大数小于最后一个标出的素数的平方,那么剩下的序列中所有的数都是素数,否则回到第二步。
  5. 本例中,因为25大于2的平方,我们返回第二步:
  6. 剩下的序列中第一个素数是3,将主序列中3的倍数划掉,主序列变成:
    • 2 3 5 7 11 13 17 19 23 25
  7. 我们得到的素数有:2,3
  8. 25仍然大于3的平方,所以我们还要返回第二步:
  9. 现在序列中第一个素数是5,同样将序列中5的倍数划掉,主序列成了:
    • 2 3 5 7 11 13 17 19 23
  10. 我们得到的素数有:2,3,5 。
  11. 因为23小于5的平方,跳出循环.
结论:2到25之间的素数是:2 3 5 7 11 13 17 19 23。

埃拉托斯特尼筛法c++实现

编辑
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
usingnamespacestd;
constlonglongmaxn=10000007+10;
constlonglongmaxp=700000;
intvis[maxn];//i是合数vis为1,i是素数,vis为0
longlongprime[maxp];
voidsieve(longlongn){
longlongm=(longlong)sqrt(n+0.5);
memset(vis,0,sizeof(vis));
vis[2]=0;
for(longlongi=3;i<=m;i=i+2){
if(!vis[i])for(longlongj=i*i;j<=n;j+=i)vis[j]=1;
if(i*i>n)break;
}
}
longlonggen(longlongn){
sieve(n);
longlongc=1;
prime[0]=2;
for(longlongi=3;i<=n;i=i+2)if(!vis[i])
prime[c++]=i;
returnc;
}
int main()
{
    freopen("in.in","r",stdin);
    freopen("biao.out","w",stdout);
longlongn,c;
cout<<"刷素数到n:";
cin>>n;
c=gen(n);
for(longlongi=0;i<c;i++)
printf("%lld",prime[i]);
cout<<endl<<c;
return0;
}

埃拉托斯特尼筛法python实现

编辑
def primes(n):
    P = []
    f = []
    for i in range(n+1):
        if i > 2 and i%2 == 0:
            f.append(1)
        else:
            f.append(0)
    i = 3
    while i*i <= n:
        if f[i] == 0:
            j = i*i
            while j <= n:
                f[j] = 1
                j += i+i
        i += 2

    P.append(2)
    for x in range(3,n,2):
        if f[x] == 0:
            P.append(x)

    return P

n = 100   #100以内的素数
P = primes(n)
print P
词条标签:
理学