# Listing the first 100 prime numbers

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
{
}

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

}

System.out.println(list);

• You may wanto to take a look at Sieve of Eratosthenes. Here and here. – Bruno Costa Feb 7 '15 at 17:44
• @BrunoCosta He is pretty much doing a sieve, except for the fact that he doesn't care about the primes after. – TheCoffeeCup Feb 7 '15 at 17:53
• No, @MannyMeng, this is not a sieve. He's testing each number for divisibility by each preceding prime. Sieves generate multiples of each prime and eliminate them, which is considerably more efficient. – itsbruce Feb 7 '15 at 23:02

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>();
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) {
}
number++;
count = list.size();
}
System.out.println(list);


• 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) {
}
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) {
}
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) {
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) {
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]) {
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]) {

• Don't use break to leave the for loop like that, because then someone has to be looking for the branch. Instead, just change the condition of the loop to: for (int i = 0; isPrime && i < list.size(); i++) – apnorton Feb 7 '15 at 22:23