prime number generator

[JeffK31]

Hi all,

I am attempting to teach myself java from a tutorial webpage. One of the exercises is to write a program to calculate the first 100 prime numbers. Here's what I came up with:



class Prime {
public static void main(String[] arguments) {
int number = 2;
int primes = 1;
System.out.println("Prime #" + primes + " is " + number);
number++;
primes++;

// keep a count of prime numbers
while (primes <= 100) {

// test each number for primeness
for (int divisor = 2; divisor < number; divisor++) {
if (number % divisor == 0) {
number++;
continue;}

}

// print prime numbers
System.out.println("Prime #" + primes + " is " + number);
number++;
primes++;}
}
}



The program compiles just fine. When I ran it, it appeared to run just fine... until I realized that not all the numbers it's returning as prime actually are. It lists 2, 3, 5, 7, 11, 13, 17, 19, 23 (so far so good), 27(?), 29, 31, 35(?), 37, 41, and so on. Every once in a while a composite number sneaks into the list and I have no idea why. Browsing other threads, it's clear from other people who have worked on similar programs that there are more efficient ways of doing it (for instance, since 2 is the only even prime, I only really need to test odd numbers) but it still seems like my program should work. Can anyone help?

Jeff

[Xeel]

Because inside IF: number variable changes and divisor stays on the same position it was left by the previous number value until number variable checks as a "prime" number.

For example we try number = 24: by the time number equals 27 divisor is already 14. So for number=27 we run divisor from 14 till 26 and 27 never is fully divided so it gets into the list of primes that is obviously wrong.

Reinitialize divisor every time you change the number.

It's all can be clearly seen using any debugger...

[dlorde]

To speed it up, you can try dividing only by odd numbers less than half the target number. To speed it up even more, store the primes already calculated and divide only by them (again for values up to half the target). And so-on ;-)

Doing more things faster is no substitute for doing the right things...
S. R. Covey

[JeffK31]

Xeel,

That was indeed the problem. Thanks very much.

Jeff