1
\$\begingroup\$
public static List<Integer> storePrimes(){
        int limit = Integer.MAX_VALUE / 10;
        boolean primes[] = new boolean[limit];
        List<Integer> primeList = new ArrayList<Integer>();
        int i = 2;
        while(primeList.size() <= 10001){
            while(true){
                if(primes[i] == false){
                    primeList.add(i);
                    break;
                }
                i++;
            }

            for(int j = i; j < limit; j += i){
                primes[j] = true;
            }
            i++;
        }
        return primeList;
    }

I want to find Nth primes. I am using this function to store all N primes. Later I can easily get Nth prime from list instead of doing everytime. N here is 10000.

How could I improve this code? What is the best upperlimit of an array?

\$\endgroup\$
2
\$\begingroup\$

How many?

How many primes are there less than N?

The short answer is that you should have somewhere between 100,000 and 1,000,000 entries in the array. There's a table that says that there are less than 10,000 primes before 100,000.

        int limit = Integer.MAX_VALUE / 10;

You can calculate this based on N. So assuming you pass N as a parameter to the method:

        final int LIMIT = 2 * N * (int)Math.log(N);

Would contain the necessary number of primes consistently. You could probably get away with a considerably smaller number than 2. E.g. 1.1 would likely also work.

I made LIMIT final and capitalized it. It's not going to change, so we may as well make note of that.

Match name to function

        boolean primes[] = new boolean[limit];

You call this primes, but the prime values are false. I would change this to composites. Then it makes more sense for false to mean that it is prime. You may even want to call it something like compositeStatuses or factorableStatuses to make that meaning clearer.

Optimize

            for(int j = i; j < limit; j += i){

You can actually do fewer than this:

            for (int j = i * i; j < LIMIT; j += i) {

This works because the first i multiples will have already been marked false by previous primes. For example, when i is 2, then this starts at 4. For 3, this starts at 9. The only multiple between 3 and 9 is 6 which was marked false when i was 2. In general, if a multiple is less than i * i, it will have been seen previously because it must be a multiple of i and something smaller than i. All primes smaller than i have already been found. The i * i value is the first multiple that we've never seen previously.

I added some extra spaces for readability as well.

Readability

        while(primeList.size() <= 10001){
            while(true){
                if(primes[i] == false){
                    primeList.add(i);
                    break;
                }
                i++;
            }

            for(int j = i; j < limit; j += i){
                primes[j] = true;
            }
            i++;
        }

I would find this easier to read as

        for (int i = 2; i < LIMIT; i++) {
            if (composites[i] == false) {
                primeList.add(i);
                if (primeList.size() >= N) {
                    break;
                }

                for (int j = i * i; j < LIMIT; j += i) {
                    composites[j] = true;
                }
            }
        }

This also explicitly handles the case where you try to go past the end of the array. And it returns just N primes. The original code would return 10,002 primes when you only needed 10,000.

I find it easier to follow without the infinite loop. Now we can see that we are iterating from 2 to LIMIT checking if each value is prime. There's only one loop that changes i so it's easy to understand what happens on each iteration.

\$\endgroup\$
  • \$\begingroup\$ Don't compare if (composites[i] == false). Just use if(!composites[i]) \$\endgroup\$ – FredK Jun 7 '16 at 18:02

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.