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

1. ## sieve of eratosthenes

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

2. ## Re: sieve of eratosthenes

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

`if (num % 2 == 0)`

3. ## 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;
}
}```

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

rsala004 (October 27th, 2009)

5. ## Re: sieve of eratosthenes

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.

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

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

}

}

}```