....................
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.
....................
Last edited by rsala004; December 29th, 2010 at 10:53 AM.
To check if a number is even, you can do this:
if (num % 2 == 0)
The Java API: http://java.sun.com/javase/6/docs/api/
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 10:32 AM.
rsala004 (October 27th, 2009)
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 11:15 AM.
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 04:07 PM.
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] + ","); } } } }