sieve of eratosthenes

• October 27th, 2009, 05:55 AM
rsala004
sieve of eratosthenes
....................
• October 27th, 2009, 07:36 AM
literallyjer
Re: sieve of eratosthenes
To check if a number is even, you can do this:

Code :

`if (num % 2 == 0)`
• October 27th, 2009, 08:52 AM
helloworld922
Re: sieve of eratosthenes
A better way is too look for the next number that's not zero, and start marking off it's multiples. Also, remember in a sieve you can't go to just the sqrt(bound), you have to go through the entire array, marking off all the multiples. Another efficiency modification you can make is to increase your inner for loop by the value you're marking off (that's the multiple you're marking off), rather than by 1. Also, it's not necessary to have an array that contains numbers, but just true/false for prime/non-prime (a tricky optimization is to have prime=false and non-prime=true).

Code :

```for (int i = 2; i < primes.length; i++) { if (primes[i] == true) { continue; } for (int j = i + i; j < primes.length; j += i) { primes[j] = true; } }```
• October 27th, 2009, 10:12 AM
rsala004
Re: sieve of eratosthenes
Quote:

Originally Posted by helloworld922
A better way is too look for the next number that's not zero, and start marking off it's multiples. Also, remember in a sieve you can't go to just the sqrt(bound), you have to go through the entire array, marking off all the multiples. Another efficiency modification you can make is to increase your inner for loop by the value you're marking off (that's the multiple you're marking off), rather than by 1. Also, it's not necessary to have an array that contains numbers, but just true/false for prime/non-prime (a tricky optimization is to have prime=false and non-prime=true).

^:)^

thanks, i think thats exactly what i was looking for.

but also with this sieve i think actually once you progress through 1 -> sqrt(n) you cover all non-prime multiples.
Quote:

Algorithm
To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the first prime number.
3. Strike from the list all multiples of p greater than p.
4. Find the first number remaining on the list greater than p (this number is the next prime); let p equal this number.
5. Repeat steps 3 and 4 until p^2 is greater than n.
6. All the remaining numbers on the list are prime.

• October 27th, 2009, 03:04 PM
helloworld922
Re: sieve of eratosthenes
False, all multiples are non-prime :D All the multiples in the sieve of eratosthenes must be marked off

You only use the sqrt trick when you're checking if a number is prime by running through the multiples.

Ex: is 100 prime?

only have to check integers from 1 to sqrt(100) by using the "naive" primality checker.

However, if you use the sieve, you must mark all multiples of 2 up to 100, all multiples of 3 up to 100, all multiples of 5 up to 100... etc.

this could have been why you were getting 49 being marked as prime.

If you're bound was 100, then it would mark:

2,3,5,7 as being prime correctly, but everything else greater than 10 would be marked as prime (or, not marked as non-prime)

Take a look at the animated picture on wikipedia's website about the sieve of eratosthenes, and you'll see they're marking up to bound, not just sqrt(bound) :)
• December 29th, 2010, 09:37 AM
vasidi
Re: sieve of eratosthenes
I'm new in programming and I was looking for a simple code for the Sieve of Eratosthenes and all I found was optimized and a little difficult for understanding code..so I want to post this one for the beginners like me.:)

Code Java:

```  public class Erathostenes { private static int MAX = 10000; /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub     int [] numbers = new int[MAX]; int [] primes = new int[MAX]; // 0 = not used ; 1 = prime ; -1 = erased   // initialize the arrays for(int i = 0; i < MAX; i++) { numbers[i] = i; }     primes[0] = primes[1] = -1; //crossing 0 and 1   for(int idx = 2; idx < MAX; idx++) { // check if erased if(primes[idx] < 0) { // erased, skip it continue; }   // the first not erased is prime primes[idx] = 1;   // check and erase for(int i = idx+1; i < MAX; i++) {   // check if erased if(primes[i] < 0) { // erased, skip it continue; }   if(numbers[i] % numbers[idx] == 0) { // erase primes[i] = -1; } } }     for(int i = 0; i < MAX; i++) {   if(primes[i] > 0) { System.out.print(numbers[i] + ","); }   }   }   }```