Java -- Prime number algorithm returns 16

2
votes

I want this Java program to stream 10001 prime numbers, but it inexplicably decides to label 16 as a prime number.

The algorithm here is just keeping a running count of prime numbers, and checking each new number to see if it is divisible by any of the primes less than it. If it isn't, then it is added to the array primes[ ], the number is displayed on the console, and the process continues, until primes[ ] is full.

public static void main(String[] args){
    int[] primes = new int[10001];
    int primeCount = 1;
    int testNumber = 3;
    primes[0] = 2;
    while(primeCount < 10001){
        for (int i = 0; i < primeCount; i++){
            if (testNumber % primes[i] == 0){
                i = 0;
                testNumber++;
            }
        }
        primes[primeCount] = testNumber;
        System.out.println(testNumber);
        primeCount++;
        testNumber++;

    }
}

Console readout:

   
3
5
7
11
13
16
17
19
.
.
.

Everything else looks to be in order except for the 16... any ideas?

3
javaprimes
Are you checking 16 against 2? It seems like your code doesn't check against 2 (prime number). - Holden Lewis
Ever heard of the sieve of Eratosthenes? Why make up a new, incorrect algorithm? en.wikipedia.org/wiki/Sieve_of_Eratosthenes - duffymo
@krico Sounds like Project Euler. - Code-Apprentice
I think you should definitely rethink design of your algorithm. Although it works (after setting i=-1) it is completely unreadable. Changing i INSIDE the for loop is never a good idea. It will cause you a lot of trouble in future. - Kylo
If you're inner for loop is using the variable i and is set to increment after each loop, you really shouldn't be touching the i value within the loop. It's not good coding. - Andrew Martin

3 Answers

6
votes

You should set i = -1 instead of i = 0 since you are immediately increasing the value of i after setting it to zero.

I recommend you to fresh up your mind with how for loop works.

4
votes

For software programming perspective you should not use a for loop inside that while loop. You should loop until if you see that it is not a prime number or you check all of possibilities and consider that it is a prime cos of you could not find any divider. So you should have a while loop inside the bigger while. I mean:

public static void main(String[] args) {
    int[] primes = new int[10001];
    int primeCount = 1;
    int testNumber = 3;
    primes[0] = 2;
    while (primeCount < 10001) {
        boolean isPrime = true;
        int i = 0;
        while (isPrime && i < primeCount) {
            if (testNumber % primes[i] == 0) {
                i = 0;
                testNumber++;
                isPrime = false;
            } else {
                i++;
            }
        }
        if (isPrime) {
            primes[primeCount] = testNumber;
            System.out.println(testNumber);
            primeCount++;
            testNumber++;
        }

    }
}
0
votes

here is the fixed version of your program

public static void main(String [] args){

        int[] primes = new int[10001];
        int primeCount = 1;
        int testNumber = 3;
        primes[0] = 2;
        while(primeCount < 10001){
            for (int i = 0; i < primeCount; i++){

                if (testNumber % primes[i] == 0){
                    i = -1;
                    testNumber++;
                }
            }
            primes[primeCount] = testNumber;
            System.out.println(testNumber);
            primeCount++;
            testNumber++;

        }
    }