如何編寫使用Eratosthenes篩選列出素數的函數

我應該編寫一個函數或腳本，使用「Eratosthenes篩」來避免不必要的存儲，找到所有素數p小於給定整數n> 2的函數或腳本（I可以創建長度爲n的矢量，但不多）如何編寫使用Eratosthenes篩選列出素數的函數

n = input('Enter your number'); 
v=[1:n]; 
v(1)=0 
for i=2:n 
    s=0; 
    for j=v(2) 
     if i>v(2) && mod(i,j)==0 
      s=s+1; 
     end 
    end 
    if s>0 
     v(i)=0; 
    end 
end 
for i=v(v>v(find(v,1,'first'))):n 
s=0; 
    for j=v(v>v(find(v,1,'first'))) 
     if i>v(v>v(find(v,1,'first'))) & mod(i,j)==0 
      s=s+1 
     end 
    end 
    if s>0 
     v(i)=0; 
    end 
end  

v

我知道這是從很遠的是我米應該寫的代碼。但這是我想到的唯一想法，它只能刪除可被2和3整除的數字，並且我需要找到所有素數，對每個條目重複此操作。這顯然不夠智能。但我覺得可以爲此創建一個循環。但我沒有編寫這個循環。請幫忙。

來源

2013-04-25 Pilot

什麼是您的具體問題？請具體說一下，「爲我解決這個問題」不是一個好問題。 – jazzbassrob 2013-04-25 19:19:36

這裏是僞代碼（對不起，我不知道matlab）。我查看了wikipedia上的算法並使用Java進行了測試。

fill your array with numbers from 2 to N 

p=2 
while p<=n 
    for i=2*p, while i<=N, increment i=i+p 
     mark element as 0 
    end for 
    increment p by 1 
end while 

print all array elements that are not 0

來源

2013-04-25 19:19:23

WP也表示最好從p * p開始。 :) – 2013-04-26 18:57:46

我同意。正如WP所述，他也可以在陣列中只使用奇數 – 2013-04-26 19:30:35

翻譯從戈蘭Belfinger的答案Matlab的代碼（我怕我跟不上你的OP代碼）：

N = input('Enter your number: '); 

primes = 2:N; 
p=2; 

while (p <= N) 
    for i = 2*p:p:N 
     primes(i - 1) = 0; 
    end; 
    p = p + 1; 
end 

primes = primes(primes > 0)

來源

2013-04-26 06:45:43 Dan

如何編寫使用Eratosthenes篩選列出素數的函數

回答

相關問題