-
埃拉託斯特尼篩法
鎖定
埃拉託斯特尼篩法，簡稱埃氏篩或愛氏篩，是一種由希臘數學家埃拉託斯特尼所提出的一種簡單檢定素數的算法。要得到自然數n以內的全部素數，必須把不大於根號n的所有素數的倍數剔除，剩下的就是素數。
- 中文名
- 埃拉託斯特尼篩法
- 外文名
- sieve of Eratosthenes
- 別 名
- 篩法
- 提出者
- 埃拉託斯特尼
- 提出時間
- 250年
- 適用領域
- 數論
- 應用學科
- 數學
埃拉託斯特尼篩法算式
給出要篩數值的範圍n，找出以內的素數。先用2去篩，即把2留下，把2的倍數剔除掉；再用下一個質數，也就是3篩，把3留下，把3的倍數剔除掉；接下去用下一個質數5篩，把5留下，把5的倍數剔除掉；不斷重複下去......。
埃拉託斯特尼篩法步驟
詳細列出算法如下：
- 列出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 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 3 5 7 9 11 13 15 17 19 21 23 25
- 如果這個序列中最大數小於最後一個標出的素數的平方，那麼剩下的序列中所有的數都是素數，否則回到第二步。
- 本例中，因為25大於2的平方，我們返回第二步：
- 剩下的序列中第一個素數是3，將主序列中3的倍數劃掉，主序列變成：
- 2 3 5 7 11 13 17 19 23 25
- 我們得到的素數有：2，3
- 25仍然大於3的平方，所以我們還要返回第二步：
- 序列中第一個素數是5，同樣將序列中5的倍數劃掉，主序列成了：
- 2 3 5 7 11 13 17 19 23
- 我們得到的素數有：2，3，5 。
- 因為23小於5的平方，跳出循環.
結論：2到25之間的素數是：2 3 5 7 11 13 17 19 23。
埃拉託斯特尼篩法Pascal實現
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.
埃拉託斯特尼篩法c++實現
#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;
}
埃拉託斯特尼篩法Java實現
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);
}
}
埃拉託斯特尼篩法python實現
# 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))
埃拉託斯特尼篩法ES6實現
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) //打印
}
埃拉託斯特尼篩法參見
- 三胞胎素數
- 素數判定法則
