Finding Primes using Algorithm in MATLAB

[sara_87]

Hi all, i understand the following however i don't know how to put this on matlab.
any help or hints will be very appreciated.

The following algorithm enables us to identify the prime number up to a given integer N, by eliminating all non-primes in that interval. It starts from a lower end.

Start with 2, which is kept as prime. Eliminate all numbers divisible by 2 up to N.

Move then to the next bigger number that has not been eliminated, which is 3. Keep it as prime and eliminate all numbers divisible by 3 up to N.

Move then to the next bigger number that has not been eliminated, which is 5; etc.

When you reach N, all non-primes have been eliminated up to N.
Write a function M-file on the basis of this algorithm for an arbitrary upper bound N.

thank you

 

[CompuChip]

The algorithm is called the sieve of Eratosthenes. If you Google "sieve of Eratosthenes" +matlab you will surely find something.

 

[sara_87]

thank you
i did find many pages about it but they are all very vague and i didnt understand them.
does anyone know how to do it..or at least how to start it because i have no idea.

 

[CompuChip]

The bad news is I don't know any MatLab at all. But I did write the following code in Mathematica, perhaps it will be of use for you (lines starting with // are comments):

// Set the upper bound [I]n[/I]
n = 100;
// Make a list of n elements, and declare them all to be primes
primes = Table[True, {n}];
// ... except 1 of course :)
primes[[1]] = False;
// Now go through all numbers [I]i[/I] between 2 and [I]n[/I]
For[i = 2, i <= n, i++,
 // for each such [I]i[/I], go through all multiples 2[I]i[/I], 3[I]i[/I], ..., [([I]n[/I]/[I]i[/I])[I]i[/I]]
 For[j = 2, j <= Floor[n/i], j++, 
  // such a multiple is NOT prime
  primes[[j*i]] = False
  ]
 ]
 // Which elements are primes (and get rid of nested lists, for aesthetic reasons)
 Position[primes, True] // Flatten

Output for n = 100:
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

That's my algorithm. I think Matlab also handles lists very well, so this should be implementable. Note that this approach really does the "sieving", another possibility would be to start with an empty list and add primes as they are found.

As an aside, Mathematica can do it in one line with the somewhat cryptic but quite efficient
Complement[Range[2, n], Flatten[Outer[Times, Range[2, Sqrt[n]], Range[2, n/2]]]]
however I don't think MatLab can do it, nor that it is pedagogically very good to do [/size]