sieve of eratosthenes

**rsala004** · October 27th, 2009, 05:55 AM

....................

**literallyjer** · October 27th, 2009, 07:36 AM

To check if a number is even, you can do this:

if (num % 2 == 0)

**helloworld922** · October 27th, 2009, 08:52 AM

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).

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;
			}
		}

**rsala004** · October 27th, 2009, 10:12 AM

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.

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.

**helloworld922** · October 27th, 2009, 03:04 PM

False, all multiples are non-prime

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)

**vasidi** · December 29th, 2010, 10:37 AM

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.

 
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] + ",");
			}
 
		}
 
	}
 
}

Thread: sieve of eratosthenes

LinkBack

Thread Tools

Display

sieve of eratosthenes

Related threads:

Re: sieve of eratosthenes

Re: sieve of eratosthenes

The Following User Says Thank You to helloworld922 For This Useful Post:

Re: sieve of eratosthenes

Re: sieve of eratosthenes

Re: sieve of eratosthenes