Listing the first 100 prime numbers

Question

I thought of this implementation, and I want to get feedback from you.. what design would you use for printing first 100 prime numbers?

I used the fact that, if the number is not divisible by any prime less than itself, it will be a new prime.

    ArrayList<Integer> list = new ArrayList<Integer>();
    list.add(2); // first prime 2 goes to our collection
    int count = list.size(); // count is our size it will be max 100
    int number = 3;  // first prime number after 2 is 3

    while ( count != 100 ) // we want first 100 prime
    {
        boolean isPrime = true; // we assume that the number is prime
        for ( int i = 0; i < list.size(); i++ )
        {
            if ( number % list.get(i) == 0 ) // we check for every less prime
                isPrime = false; // however, if it is divided by any other less prime, isPrime will be false

        }

        if ( isPrime ) // if it stays true, we will add it to our collection
        {
            list.add(number);
        }

        number++; // we try every number
        count = list.size(); // count equals size of collection at every turn

    }

    System.out.println(list);

Answer 1

Some notes:

Your bracing does not follow standard Java conventions. This is more of a matter of preference, but this is how I would format your code:

ArrayList<Integer> list = new ArrayList<Integer>();
list.add(2);
int count = list.size();
int number = 3; 

while (count != 100) {
    boolean isPrime = true;
    for (int i = 0; i < list.size(); i++) {
        if (number % list.get(i) == 0) {
            isPrime = false;
        }
    }
    if (isPrime) {
        list.add(number);
    }
    number++;
    count = list.size();
}
System.out.println(list);

Some other points about formatting:

• I have removed some excess blank spaces and lines.
• I put braces around all the statements inside the if statement without braces.

Now, to the loop:

while (count != 100) {
    boolean isPrime = true;
    for (int i = 0; i < list.size(); i++) {
        if (number % list.get(i) == 0) {
            isPrime = false;
        }
    }
    if (isPrime) {
        list.add(number);
    }
    number++;
    count = list.size();
}

This could easily be a for loop:

for (int count = 1, number = 3; count < 100; number++) {
    boolean isPrime = true;
    for (int i = 0; i < list.size(); i++) {
        if (number % list.get(i) == 0) {
            isPrime = false;
        }
    }
    if (isPrime) {
        list.add(number);
    }
    count = list.size();
}

Also, all your list.size(). You can remove many of the calls:

for (int count = 1, number = 3; count < 100; number++) {
    boolean isPrime = true;
    for (int i = 0; i < list.size(); i++) {
        if (number % list.get(i) == 0) {
            isPrime = false;
        }
    }
    if (isPrime) {
        list.add(number);
        count++;
    }
}

You can also remove much of the iterations of the inner loop by breaking when isPrime is true, or just:

for (int count = 1, number = 3; count < 100; number++) {
    for (int i = 0; i < list.size(); i++) {
        if (number % list.get(i) == 0) {
            list.add(number);
            count++;
            break;
        }
    }
}

But the main thing is, your code is not as efficient as it could be. Try a Sieve:

List<Integer> result = new LinkedList<Integer>();
int n = 1.4 * 100 * Math.log(100);
boolean[] isPrimeArray = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
    isPrimeArray[i] = true;
}
for (int i = 2, primesLeft = 100; i * i <= n && primesLeft > 0; i++) {
    if (isPrimeArray[i]) {
        result.add(i);
        primesLeft--;
        for (int j = i; i * j <= n; j++) {
            isPrimeArray[i * j] = false;
        }
    }
}
System.out.println(result);

The sieve does:

1. Sets all numbers to true (as in, is a prime).
2. Starts at 2, and works its way through the primes. While doing that, marks all the multiples of a prime to false.
3. If it has 100 primes, the loop will terminate.
4. Print the result.

Also you have 100 as a magic number. Set it as a field:

private static final int MAX = 100;

// Code here

Use:

List<Integer> result = new LinkedList<Integer>();
int n = 1.4 * MAX * Math.log(MAX); // Overestimate by 40%
boolean[] isPrimeArray = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
    isPrimeArray[i] = true;
}
for (int i = 2, primesLeft = MAX; i * i <= n && primesLeft > 0; i++) {
    if (isPrimeArray[i]) {
        result.add(i);
        primesLeft--;
        for (int j = i; i * j <= n; j++) {
            isPrimeArray[i * j] = false;
        }
    }
}
System.out.println(result);

This will result in a much faster result.