I've been using a for loop with with mod functions to sieve number from the Natural numbers. Is there a more efficient sieve technique than this.

Question

Jesse Crotts 2016-11-1

评论： Walter Roberson 2016-11-2

My Code looks something like this

P = primes(100000);
N = 1999900000:1:2000000000;
for i = 1:numel(P);
    N(mod(N,P(i))==P(i)+1) = [];
    N(mod(N,P(i))==P(i)-1) = [];
end

Answer 1

Walter Roberson 2016-11-1

Certainly. You do not need to do the mod: you can mark off the multiples as being non-prime. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Jesse Crotts 2016-11-1

I was hoping to not use a for loop. is there much of a way to not use it.

Walter Roberson 2016-11-2

[n, p] = ndgrid(N, P);
is_composite = mod(n, p) == 0;
which_are_composite = any(is_composite, 1);

However, you had asked for a more efficient sieve technique, not one that would thrash your hard disk for a couple of days.