0

我应该编写一个函数或脚本，使用“Eratosthenes 筛”找到所有小于给定整数 n>2 的素数 p，从而避免不必要的存储（我可以创建长度为 n 但不能更多的向量）

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 整除的数字，我需要通过对每个条目重复此操作来找到所有素数。这显然不聪明。但我觉得可以为此创建一个循环。但我没有编写这个循环。请帮忙。

4

2 回答 2

2

翻译 Goran 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-26T06:45:43.913 回答
2

这是伪代码（对不起，我不知道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-25T19:19:23.750 回答