- 中文名
- 埃拉托斯特尼筛法
- 外文名
- 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。
var
f:array[1..100]of boolean; //存储是否是质数
i,j,n:longint;
begin
readln(n);
fillchar(f,sizeof(f),true); //先假设都是质数
f[1]:=false; //注意：1不是质数
for i:=2 to trunc(sqrt(n)) do begin //优化：只需考虑根号n以内的数的倍数
if not f[i] then //优化：如果一个数不是质数，那么它的倍数一定已经被除去了
continue;
for j:=2 to n div i do //除去它的倍数
f[i*j]:=false;
end;
for i:=1 to n do //输出
if f[i] then
write(i,' ');
writeln;
end.
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 10000007 + 10;
const long long maxp = 700000;
int vis[maxn]; // i是合数vis为1，i是素数，vis为0
long long prime[maxp];
void sieve(long long n){
long long m = (long long)sqrt(n + 0.5);
memset(vis, 0, sizeof(vis));
vis[2] = 0;
for (long long i = 3; i <= m; i += 2) {
if(!vis[i])
for (long long j = i * i; j <= n; j += i)
vis[j] = 1;
if(i * i > n)
break;
}
}
long long gen(long long n){
sieve(n);
long long c = 1;
prime[0] = 2;
for (long long i = 3; i <= n; i += 2)
if(!vis[i])
prime[c++] = i;
return c;
}
int main()
{
long long n, c;
cout << "刷素数到n：";
cin >> n;
c = gen(n);
for (long long i = 0; i < c; i++)
printf("%lld", prime[i]);
cout << endl << c;
return 0;
}
public class assf
{
public static void main(String[] args)
{
int aa[]=new int [101];
aa[2]=0;
int k=2,tt=0;
while(tt<101)
{
for(int i=1; i<aa.length; i++) //将不是素数的数筛出
{
if(i%k==0&&i!=k) aa[i]=1;
}
for(int i=1; i<aa.length; i++) //将筛选后的第一个数当做新的筛子
{
if(i>k&&aa[i]==0)
{
k=i;
break;
}
}
tt++;
}
for(int i=1; i<aa.length; i++)
if(aa[i]==0) System.out.printf("%d ",i);
}
}
# coding=UTF-8
def prinum(num=100, jud=True):
"""埃拉托斯特尼筛法 Sieve of Eratosthenes"""
try:
if num<2:
return False if jud else list()
elif num==2:
return True if jud else [2]
else:
num=num if isinstance(num, int) else int(num)+1
except:
raise ValueError("'num' must be a real number")
prili=[2]
prili.extend(list(range(3, num+1, 2)))
i=0
while prili[i]**2 < prili[-1]:
i+=1
for j in range(prili[i]**2, prili[-1]+1, prili[i]):
if j==num and jud:
return False
if j in prili:
prili.remove(j)
return (True if num in prili else False) if jud else prili
if __name__=="__main__":
"""
默认输入的数字 num=100，默认jud=True
若 jud=True 则函数 prinum 功能为判断输入的数字是否为质数，这是默认项
若 jud=False 则函数 prinum 功能为以列表形式返回 2 到 num 的质数
"""
print(prinum(jud=False))
function* even(){//初始序列:3,5,7,9...
let n = 1
while(true){yield n+=2}
}
function* primes(max){
yield 2
var it = even(),n=null
while(true){
n = it.next().value
if(n>max){break}
yield n
it = (function*(it,n){
for(let x of it){
if(x%n>0){yield x} //筛选后续数值
}
})(it,n)
}
}
let Primes = primes(100) //100以内的质数
for(let x of Primes){
console.log(x) //打印
}
- 三胞胎素数
- 素数判定法则
