Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 6 of 6

Thread: sieve of eratosthenes

  1. #1
    Member
    Join Date
    Jul 2009
    Posts
    31
    Thanks
    3
    Thanked 6 Times in 5 Posts

    Default sieve of eratosthenes

    ....................
    Last edited by rsala004; December 29th, 2010 at 10:53 AM.


  2. #2
    Member
    Join Date
    Oct 2009
    Posts
    52
    Thanks
    0
    Thanked 6 Times in 5 Posts

    Default Re: sieve of eratosthenes

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

    if (num % 2 == 0)

  3. #3
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

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

    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;
    			}
    		}
    Last edited by helloworld922; October 27th, 2009 at 09:32 AM.

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

    rsala004 (October 27th, 2009)

  5. #4
    Member
    Join Date
    Jul 2009
    Posts
    31
    Thanks
    3
    Thanked 6 Times in 5 Posts

    Default Re: sieve of eratosthenes

    Quote Originally Posted by helloworld922 View Post
    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.
    Last edited by rsala004; October 27th, 2009 at 10:15 AM.

  6. #5
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: sieve of eratosthenes

    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)
    Last edited by helloworld922; October 27th, 2009 at 03:07 PM.

  7. #6
    Junior Member
    Join Date
    Dec 2010
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

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

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