Sieve of Eratosthenes

[code]

Hi,
For the lesson Arrays, I have to make a program that generates a list of prime numbers using the sieve of eratosthenes. Also this program should ask the user to enter the number up to which the program is to search for prime. In addition there is a hint that elimination may be done by assigning 0 to certain elements of the array. I'm confused as to how to do this program. Any help in the form ideas, codes, program bits will be helpful
Thanks

[Cervantes]

first thing to do is create your array. Say n is the number below which we will search for primes.

code:

var primes : array 2 .. n of int for i : 2 .. n               % edit: I've fixed this now     primes (i) := i end for

Now we need to go through and eliminate all entries in our array that are a multiple of 2.

code:

for i : 1 .. n     if primes (i) mod 2 = 0 then         primes (i) := 0     end if end for

Now we need to do the same for 3:

code:

for i : 1 .. n     if primes (i) mod 3 = 0 then         primes (i) := 0     end if end for

Of course, we see a pattern emerging, here. Do you see it? We should use another for loop to run through all the primes we've got. If the element is a 0, go on to the next; otherwise, run through a for loop like the ones shown above to remove all multiples of that current element.

Try to code that. Post back your successes or failures.

[code]

Thanks a lot for the help !

I'm having a few problems. Firstly, in your 1st code primes (i)=i (It shows Array subscript out of range, I dont understand why)
Also, After i go through all the numbers and turn all non prime number to 0, how do i display the prime numbers.
If i use command put primes(i) , It shows error that i has no value.
Also, can u please give me an example of a loop in which i can set the conditions such as, If its 0 go to the next number, if not then run though the loop , turn the number into 0 and then go on to the next number(continues till the loop has gone through all the numbers till n).

Please post back regarding this and if possible soon since this is due on Monday and I'm running out of time .

[Cervantes]

Sorry, I made a mistake. I changed the array to start with a lower bound of 2, but forgot to change the for loop. See, the for loop starts with i=1. Then I said, primes (i) := i, but the first time that runs through, we're trying to assign 1 to primes (1), but primes (1) doesn't exist, because the array starts at 2.

After you've turned all non-prime numbers to zero, you would display them by doing something like this:

code:

for i : 2 .. n     if primes (i) not= 0 then         put primes (i)     end if end for

put primes (i) is meaningless unless i has some value. We use a for loop to run i through all possible indeces for our array.

I think you need to get a better understanding of arrays. I suggest reading at least part of this tutorial.Hopefully a second look at arrays will help you to understand them.

code wrote:

Also, can u please give me an example of a loop in which i can set the conditions such as, If its 0 go to the next number, if not then run though the loop , turn the number into 0 and then go on to the next number(continues till the loop has gone through all the numbers till n).

This would be a for loop on i that contains an if statement. The if statements tests whether primes (i) is not zero. If it is not zero, then do all that stuff. Otherwise, do nothing. In other words, don't provide an else clause. All that stuff will be skipped if it is zero, and then we'll reach the end of the code inside the for loop and incriment i and start again.

[Piro24]

Couldn't you just use an array with the maximum bounds of the number of primes...

Use it to store all of the primes from 1 - whatever.

Run it through 2 fors to get each prime...

code:

var n, count, c : int := 0 put "How many numbers to be scanned?" get n var prime : array 1 .. n of int for i : 1 .. n     count := 0     for j : 1 .. i         if i rem j = 0 then             count += 1         end if     end for     if count <= 2 then         c += 1         prime (c) := i     end if end for

[Windsurfer]

This sounds like someone getting their homework done for them isn't there a policy here or something...?