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
  • 3
    \$\begingroup\$ You may wanto to take a look at Sieve of Eratosthenes. Here and here. \$\endgroup\$ Feb 7, 2015 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\$ Feb 7, 2015 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, 2015 at 23:02

1 Answer 1

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\$
2
  • \$\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, 2015 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, 2015 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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