Как написать функцию, которая выводит список простых чисел с помощью решета Эратосфена

Я должен закодировать функцию или скрипт, который находит все простые числа p меньше заданного целого числа n > 2, используя «решето Эратосфена», избегая ненужного хранения (я могу создать вектор длины 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, и мне нужно найти все простые числа, повторяя это для каждой записи. Это явно неразумно. Но я чувствую, что для этого можно создать цикл. Но я не могу закодировать этот цикл. Пожалуйста помоги.


matlab primes sieve-of-eratosthenes
person Nasibabuba    schedule 25.04.2013    source источник
comment
Каков ваш точный вопрос? Пожалуйста, будьте конкретны, решите, что это для меня не очень хороший вопрос.   -  person devrobf    schedule 25.04.2013

Ответы (2)


arrow_upward
2
arrow_downward

Вот псевдокод (извините, матлаб не знаю). Я просмотрел алгоритм в википедии и протестировал его на 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
person Goran Belfinger    schedule 25.04.2013
comment
WP также говорит, что лучше начинать с p*p. :) - person Will Ness; 26.04.2013
comment
Я согласен. Как указано на WP, он также может использовать только нечетные числа в массиве. - person Goran Belfinger; 26.04.2013

arrow_upward
2
arrow_downward

Перевод кода из ответа Горана Белфингера на Matlab (боюсь, я не смог следовать коду в вашем ОП):

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)
person Dan    schedule 26.04.2013