CODEWITHSUNDEEP
matlabprimessieve-of-eratosthenes
Nasibabuba
Nasibabuba

Reputation: 179

How to write a function that lists prime numbers using the sieve of Eratosthenes

I am supposed to code a function or script that finds all prime numbers p smaller than a given integer n>2 using the "sieve of Eratosthenes" avoiding unecessary storage(I can create a vector of length n but not more)

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

I realize that this is very far from the code that I m supposed to write. But this is the only idea that came up to my mind and it only removes numbers which are divisible by 2 and 3,and I need to find all prime numbers,by repeating this for each entry.This is obviously not smart. But I feel that there can be created a loop for that. But I am failing to code this loop. Please help.

Upvotes: 0

Views: 22305

Answers (2)

Dan
Dan

Reputation: 45752

Translating the code from Goran Belfinger's answer to Matlab (I'm afraid I couldn't follow the code in your 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)

Upvotes: 2

Goran Belfinger
Goran Belfinger

Reputation: 71

Here is the pseudocode (sorry, I don't know matlab). I looked at the algorithm on wikipedia and tested it in 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

Upvotes: 2

Related Questions