5
\$\begingroup\$

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);
\$\endgroup\$
  • 3
    \$\begingroup\$ You may wanto to take a look at Sieve of Eratosthenes. Here and here. \$\endgroup\$ – Bruno Costa Feb 7 '15 at 17:44
  • 2
    \$\begingroup\$ @BrunoCosta He is pretty much doing a sieve, except for the fact that he doesn't care about the primes after. \$\endgroup\$ – TheCoffeeCup Feb 7 '15 at 17:53
  • \$\begingroup\$ 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. \$\endgroup\$ – itsbruce Feb 7 '15 at 23:02
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ thank you for the indentation, i liked the double for loop solution.. our teacher assumes that we dont know switch-break, so i can't use it. now i am trying to analyze Sieve code.. TY \$\endgroup\$ – funky-nd Feb 7 '15 at 18:43
  • \$\begingroup\$ 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++) \$\endgroup\$ – apnorton Feb 7 '15 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.