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.

4 views (last 30 days)
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

Answers (1)

Walter Roberson
Walter Roberson on 1 Nov 2016
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
For greater efficiency still, see https://primes.utm.edu/prove/merged.html
  2 Comments
Walter Roberson
Walter Roberson on 2 Nov 2016
[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.

Sign in to comment.

Categories

Find more on Material Sciences in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!