The “sieve method of Eratosthenes” (as far as I know), is the idea that you start with a list of numbers, then remove all the multiples of the first number then the second (remaining) number etc so we would start with:
2,3,4,5,6,7,8,9,10,11,12,13,14,15,......,1000
and we first remove multiples of 2 (except itself) leaving:
2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, ......999
Then we look at the next number (3) and remove all multiples of him:
2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, .......997
Next we go for 5
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,............997
etc.
Begin by setting up a list structure (you could use an array if you are unfamiliar with other structures, but personally I don't like this idea, because it means you would still iterate over 1000 elements (999 actually) to print only the primes leftover by going through the set several times already).
then (in a javanese dialect of pseudocode):
-
counter=0;
-
while myList has more elements
-
{
-
currentElement=myList.elementAt(counter)
-
counter++;
-
counter2=counter
-
while(counter2<myList.size())
-
{
-
if ((myList.elementAt(counter2) mod currentElement)==0)
-
{
-
myList.removeElement(counter2);
-
}
-
else
-
{
-
counter2++
-
}
-
}
-
}
-
then print out the list.
I'm not certain the logic above is correct, in particular counter2 (When you remove an element you don't need to increment it <convince yourself of this, draw a picture of what's happening if need be>).
Another way to approach program (which I would still argue uses the idea of the sieve of Eratosthenes (though your teacher/lecturer may not agree)) would use 2 lists:
The first one starts with all the numbers from 2..1000, the second starts empty.
We can then iterate through the elements in the first list, only adding it to the second list if it cannot be divided by any of the elements in the second list. (I initially though this was more efficient, but have changed my mind (well implemented it would have a similar efficiency to the code above)).
thus the logic would be more like:
-
for(int i=2; i<firstList.size(); i++)
-
{
-
boolean prime=true; //some will say this is bad logic (and their kinda right)
-
for(int j=0;j<secondList.size(); j++)
-
{
-
if(firstList.elementAt(i) mod secondList.elementAt(j) == 0)
-
{
-
prime=false;
-
break; //out of the loop
-
}
-
}
-
if(prime)
-
{
-
secondList.add(firstList.elementAt(i));
-
}
-
}
-
-
I leave it to you to
a) make sure this is indeed the sieve of E
b) follow the logic to ensure it is correct
c) turn it into c (or whichever language you are using)
15
