Java Programming Help?

Question

Use the Sieve of Eratosthenes to locate and print out all prime numbers from 1 to 1000.

Follow a procedure similar to this:

1.	Write down, in order, all number to be considered.
2.	Cross out 1, since it is not considered prime.
3.	Go to the next number not crossed out; leave it, but cross out all multiples of that number.
4.	Repeat step 3 until you pas the number which is half of the largest number considered. At that point, all numbers not crossed out are the desired primes.

Your algorithm may vary slightly from the one above but speed is important.

Mark aka jack573 · Accepted Answer

You could do the following.

1. Make an array of 1000.  Put all of the numbers you are checking inside it.
2. Make a second array of 1000 that will hold true or false as to whether the number in the first array is prime.  Set them all to true.
3. As your step 2 says, cross out 1, or put false in the second array for 1.
4. Check out 2.  This is prime, so set it to true in the second array.
Now here is where you can change things, but remember, speed is important.
5. You can go through the rest of the second array and put false in every even number.
6. Check out 3, also prime.  Set it to true.  Go through the array for every 6th index from 3.  You do every 6th index, not every 3rd, as 3 + 3 is 6 and it is even.  You have already set all of the evens to false.
7. Check out 4, it is already false.  Move on.
8. Check out 5.  it is prime.  Go through the array at intervals of 10.  Similar to 3, you have removed all the even already.
Continue this pattern until you come to 500, or really 499 since you know 500 is not a prime.

You should be able to work out other ways to make it more efficient.  For instance, the 5s, 15 will already be false since it is 5x3, same with 45 - 5x9.  You have already changed all of the 3s to false.

Hope that helps.

Trending News

Java Programming Help?

1 Answer