Prime numbers (Eratosthenes)

Thread view:

JS - 29 Dec 2004 21:05 GMT

I need to implement the following algorithm where P needs to be modelled af
an array of booleans ( booleans[]P = new boolean[n + 1]).

But how do I write this in the {} thats gonna be executed as long as 2*i<=
n??

for (i = 2; 2*i <=n; i = i + 1)
//{remove from P all multiples of i};
//print the contents of P

Reply to this Message

Stefan Schulz - 29 Dec 2004 21:12 GMT

> I need to implement the following algorithm where P needs to be
> modelled af an array of booleans ( booleans[]P = new boolean[n + 1]).
[quoted text clipped - 5 lines]
> //{remove from P all multiples of i};
> //print the contents of P

First, you might wish to reconsider the loop length. It will be
sufficient to mark all multiples of primes less then the square root of
n. Then you iterate over all multiples of the current i smaller then
(or equal to) n, marking each such multiple as false.

What, you wanted me to do your homework for you? :-P Its all written
down there, and i bet in your textbook as well.

Signature

In pioneer days they used oxen for heavy pulling, and when one ox
couldn't budge a log, they didn't try to grow a larger ox. We shouldn't
be trying for bigger computers, but for more systems of computers.
--- Rear Admiral Grace Murray Hopper

Reply to this Message

Prime numbers (Eratosthenes)

Free Magazines