基本思想
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
1不是素數，去掉。剩下的數中2最小，是素數，去掉2的倍數，餘下的數是：
3 5 7 9 11 13 15 17 19 21 23 25 27 29
剩下的數中3最小，是素數，去掉3的倍數，如此下去直到所有的數都被篩完，求出的素數為：
2 3 5 7 11 13 17 19 23 29
C語言實現
1、算法一：令A為素數，則A*N（N>1;N為自然數）都不是素數。
2、
說明：解決這個問題的訣竅是如何安排刪除的次序，使得每一個非質數都只被刪除一次。 中學時學過一個因式分解定理，他說任何一個非質（合）數都可以分解成質數的連乘積。例如，16=4^2，18=2 * 3^2，691488=2^5 * 3^2 * 7^4等。如果把因式分解中最小質數寫在最左邊，有16=4^2，18=2*9,691488=2^5 * 21609,；換句話說，把合數N寫成N=p^k * q，此時q當然是大於p的，因為p是因式分解中最小的質數。由於因式分解的唯一性，任何一個合數N，寫成N=p^k * q;的方式也是唯一的。 由於q>=p的關係，因此在刪除非質數時，如果已知p是質數，可以先刪除p^2,p^3,p^4,... ，再刪除pq,p^2*q,p^3*q,...,（q是比p大而沒有被刪除的數），一直到pq>N為止。
因為每個非質數都只被刪除一次，可想而知，這個程式的速度一定相當快。依據Gries與Misra的文章，線性的時間，也就是與N成正比的時間就足夠了（此時要找出2N的質數）。 （摘自《C語言名題精選百則（技巧篇）》，冼鏡光 編著，機械工業出版社，2005年7月第一版第一次印刷）。代碼如下：
該代碼在Visual Studio 2010 環境下測試通過。
以上兩種算法在小數據下速度幾乎相同。
pascal實現
maxfactor:=trunc(sqrt(maxp));//篩法求素數
fillchar(sieve,sizeof(sieve),true);
for i:=2 to maxfactor do
if sieve[i] then
begin
newp:=i+i;
while newp<=maxp do
begin
sieve[newp]:=false;
newp:=newp+i;//每次取出這個數的倍數
end;
end;
python實現
def sundaram3(max_n):
numbers=range(3,max_n+1,2)
half=(max_n)//2
initial=4
for step in xrange(3,max_n+1,2):
for i in xrange(initial,half,step):
numbers[i-1]=0
initial+=2*(step+1)
if initial>half:
return+filter(None,numbers)
FB語言實現
dim as integer n
input n
dim as integer a(n),i,j,k,f,s
for i=2 to n
a(i)=1
next
for i=2 to int(sqr(n))
if a(i)=1 then
for j=i+1 to n
if j mod i=0 then a(j)=0
next
end if
next
s=0
for i=2 to n
if a(i)=1 then s+=1
next
print s
sleep
end
