如何编写使用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筛选列出素数的函数

回答

相关问题