3
\$\begingroup\$

I'm new here, and relatively new to coding. I wrote a method that returns an array of the n first primes. Even though my intended goal was just to find the nth prime, I ended up using an array (int[] primes) in order to minimize calculations.

My method goes iterates upwards by 2, since even numbers greater than 2 are not primes, and testing if the candidate number is a multiple of the previous primes (of course not including 2) that have been found up until the test.

Actually it does not do that test with all the previous primes, only up to the square root of the last prime found. You can take a look at my method.

public int[] primes(int n){

    int[] primes = new int[n];
    primes[0] = 2;

    int count = 1;
    int number = 3;

    boolean numberIsPrime;

    while (count < n){

        numberIsPrime = true;

        for (int i = 1; i < (int)(Math.sqrt(number)); i++) {

            if (number % primes[i] == 0){
                numberIsPrime = false;
                break;
            }

        }

        if (numberIsPrime){

            primes[count] = number;
            count++;
        }

        number = number + 2;

    }

    return primes;

}

I tested it in a main method through System.out.println(instance.primes(n)[n-1]); for n = 1 million and it took not more than 10 seconds to find the correct answer, and for n = 10 million it took no more than 4 and a half minutes to find the correct answer.

I let it run for n = 100 million, since I started writing this question, and it doesn't look like it is going to finish for an hour or so. I think mathematically I reduced calculations a lot.

Just by decreasing the test to the square root of the last prime did reduce computing time quite much.

But can it be improved, not only mathematically but also by means of code?

\$\endgroup\$
  • 3
    \$\begingroup\$ Did you ever hear about the Sieve of Eratosthenes? You don't need to check the same factors again and again. \$\endgroup\$ – πάντα ῥεῖ Jan 11 '18 at 17:47
  • 1
    \$\begingroup\$ @πάνταῥεῖ May I remind you that short answers are also acceptable? \$\endgroup\$ – Simon Forsberg Jan 11 '18 at 22:59
  • 1
    \$\begingroup\$ @maaartinus May I remind you that short answers are also acceptable? \$\endgroup\$ – Simon Forsberg Jan 11 '18 at 22:59
  • 1
    \$\begingroup\$ @SimonForsberg Sure. But that question looks that extremely badly researched and showing no efforts, I denied to move further than the comment and downvote. I'm pretty sure there are appropriate duplicates, no? \$\endgroup\$ – πάντα ῥεῖ Jan 12 '18 at 0:07
  • 1
    \$\begingroup\$ @πάνταῥεῖ Similar questions, yes, but duplicates are not handled that way here. For questions to be duplicates on Code Review, the code pretty much have to be identical. \$\endgroup\$ – Simon Forsberg Jan 12 '18 at 11:34
3
\$\begingroup\$

Watch for mixed idioms

        for (int i = 1; i < (int)(Math.sqrt(number)); i++) {

This is wasteful. All you need to do is

        for (int i = 1; primes[i] <= (int)(Math.sqrt(number)); i++) {

This only works in that it always checks too many values. i and number are not actually related here. The comparative relation is between primes[i] and number. This relies on i < primes[i] for all i.

And as noted in a comment, this puts a lot of reliance on the compiler to figure out that the square root will be constant. Consider

        int largestSmallerFactor = (int)(Math.sqrt(number));
        for (int i = 1; primes[i] <= largestSmallerFactor; i++) {

Now it's clear that we only take the square root once.

Helper method

        if (numberIsPrime){

Consider

        if (isOddPrime(number, primes)) {

Then you just need a helper method and can get rid of numberIsPrime altogether.

private boolean isOddPrime(int candidate, int[] primes) {
    int largestSmallerFactor = (int)(Math.sqrt(candidate));
    for (int i = 1; primes[i] <= largestSmallerFactor; i++) {
        if (candidate % primes[i] == 0) {
            return false;
        }
    }

    return true;
}

Optimization

Perhaps you are concerned that a method call has too much overhead. If so, consider

    nextCandidate:
    while (count < n) {
        int largestSmallerFactor = (int)(Math.sqrt(number));
        for (int i = 1; primes[i] <= largestSmallerFactor; i++) {
            if (number % primes[i] == 0) {
                continue nextCandidate;
            }
        }

        primes[count] = number;
        count++;
    }

No method overhead.

People will point out that the method is a more readable and robust solution, which it is. But if you're trying to wring out every possible efficiency, this might be better. You'd have to compile and compare both versions to see. Remember that the compiler might have an even better optimization for the method version.

Sieve of Eratosthenes

A comment suggested using the Sieve of Eratosthenes. While it is true that that's an efficient way to find primes, it is not well suited to finding the nth prime. The problem is that it checks a certain number of numbers, so there is a tendency to either overshoot or undershoot.

You can use a segmented sieve to process the sieve partially. So if you undershoot, you can continue. This also allows you to make smaller jumps, so you are less likely to overshoot.

It was asserted that a sieve avoids repeated division. That's true but it replaces it with redundant multiplication. For example, 210 is marked as not prime by the sieving operations for 2, 3, 5, and 7. Or more generally, a number divisible by 6 will be sieved by both 2 and 3. By contrast, trial division can stop as soon as it finds the first factor.

It may be that the sieve is faster on average. After all, a square root is an expensive operation. But it can do more work for a particular number than trial division does.

Here is an example of a windowed sieve which you could try to modify to this purpose. Don't forget to time it both ways.

\$\endgroup\$
  • 1
    \$\begingroup\$ In Java, I wouldn't bother with method call overhead. Inlining is pretty powerful and if a method doesn't get inlined, then there may be good reasons. +++ While I agree that over- and under-shooting is problematic, an optimized sieve wins hands down (under one minute for primes up to a few billions). +++ That all said, +1. \$\endgroup\$ – maaartinus Jan 12 '18 at 2:51

Your Answer

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