Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I am attempting problem 7 on Project Euler. I have come up with this solution which works fine for finding smaller nth prime numbers, but really lags when it comes to higher nth prime numbers. I am not quite sure where to start to make it more efficient.

public class TenThousandFirstPrime {

    public static boolean isPrime(int num) {
        if(num % 2 == 0) return false;
        for(int i = 3; i < Math.floor(Math.sqrt(num)); i += 2) {
            if(num % i == 0) return false;
        }

        return true;
    }

    public static void main(String[] args) {
        int count = 2;  
        int i = 3;
        while(count <= 10001) {
            if(isPrime(i)) {
                i += 2;
                count++;
            }
        }
        System.out.println(i);
    }
}

The solution only took a couple of minutes and I didn't expect it to be as slow as it is...

share|improve this question
4  
Re. how to make it faster, that's probably been explained in answers to some of the other questions about prime numbers. –  ChrisW Mar 23 at 1:28
    
Use solutions to previously solved problems to solve new problems. Suppose you want to know if 12347 is prime. If you have already computed the prime numbers less than or equal to root 12347, then you only need to check whether 12347 is divisible by each of them, not all the numbers up to the root. –  Eric Lippert Mar 23 at 6:49
    
Skipping every other number is smart. You could be smarter by starting i at 12, increasing by 6 each time, and then checking i-1 and i-5 for primeness in the loop. Clearly i, i-2, i-3 and i-4 are divisible by either 2 or 3. –  Eric Lippert Mar 23 at 6:56
1  
"I didn't expect it to be as slow as it is" -- The infinite loop identified in 200_success' answer and Jamal's comment explains why it's slower than slow (i.e. endless). –  ChrisW Mar 23 at 8:54
1  
I've noticed that you use i += 2;, probably because you've eliminated all multiples of 2 from the possible prime numbers. Why only for 2? Why not take that to its logical conclusion, and eliminate all multiples of every prime number you find? That's what the Sieve of Eratosthenes does - you should look into that if you want a faster prime number generator. –  Red Alert Mar 23 at 8:57
show 3 more comments

5 Answers 5

The square root calculation could just be done before the loop. Since this value does not change within the function, it doesn't need to be recalculated each time through the loop.

public static boolean isPrime(int num) {
    if (num % 2 == 0) return false;

    int squareRoot = Math.floor(Math.sqrt(num));
    for (int i = 3; i < squareRoot; i += 2) {
        if (num % i == 0) return false;
    }

    return true;
}
share|improve this answer
1  
Answer to this question suggest your answer is correct: that the repeated sqrt isn't optimized away by the JVM. –  ChrisW Mar 23 at 1:34
add comment

Your code does not work. Your main() has an infinite loop.

Trial division is a simple way to test whether a single number is prime. However, to test many numbers, you want to use the Sieve of Eratosthenes.

You isPrime() reports that 1 is prime and 2 is not. That might be acceptable if you take care to never call it with those parameters and document those special cases in JavaDoc.

share|improve this answer
1  
1. I don't see the infinite loop in main? 2. The Sieve of Eratosthenes would work well here, but there's the question of knowing in advance how large to make your table of candidates. Also it would require O(n) memory instead of O(1) as for trial division. 3. That's a good point about isPrime, but you'll notice that in fact it is only ever called with num >= 3. –  Nate Eldredge Mar 23 at 3:32
3  
@NateEldredge: count is only incremented if isPrime() returns true. Once the while loop gets a non-prime number (4 being the first one), the if will be skipped, so count will not increment. –  Jamal Mar 23 at 4:31
1  
@Jamal Actually, i will get stuck at 9. –  200_success Mar 23 at 4:45
    
@NateEldredge 2. The n th prime is approximately n ln n; it turns out that for 10000, this estimate is about 12% too low, but still it's a useful guide. In my opinion, using 100 kB for the sieve is a worthwhile expense. 3. Avoiding the erroneous cases of isPrime() is fine, but my point is that failure to document those cases is poor practice. –  200_success Mar 23 at 5:08
1  
Nate, at the point where you have so many primes that the memory matters, you would use consecutive sieves, for example make a sieve for the primes from 1 to 1 million, another for primes from 1 million to 2 millions, and so on, to keep memory use under control. –  gnasher729 Mar 23 at 13:09
add comment

I think you need <= in isPrime's for loop: because otherwise you'll decide that 25 is prime.

share|improve this answer
    
Moreover, you probably want to replace floor with ceil; due to the limited precision of floating point, Math.sqrt(25) could return 4.99999996 or something similar. –  Nate Eldredge Mar 23 at 1:57
1  
@NateEldredge This document says, "the result is the double value closest to the true mathematical square root of the argument value" ... so perhaps the result is exact (an integer value) if the argument is a perfect square. –  ChrisW Mar 23 at 2:04
    
Ok, true, assuming that your floating point implementation is able to represent small integers exactly (which most are). –  Nate Eldredge Mar 23 at 3:26
add comment

Unless your compiler is quite clever, it will calculate Math.floor (Math.sqrt (num)) on every single iteration of the loop, which will probably take three times longer than the rest of the operations.

"i < Math.floor (Math.sqrt (num))" is really, really bad. It makes your code think that squares of primes are prime (for example 9, 25, 49), but also products of consecutive twin primes, like 15 = 3x5, 35 = 5x7, 143 = 11x13 and so on.

As mentioned, the loop in main stops making progress when it reaches the first non-prime. I would write the loop in the most straightforward way:

for (int i = 3; ; i += 2)
{
    if (isPrime (i))
    {
        // Whatever you want to do with primes
    }
}

And in general, I wouldn't put lots of code into main (). main () should in my opinion process any parameters, then call code doing the work.

share|improve this answer
add comment

In your code, the i+=2 should be outside the if statement, otherwise it gets stuck on the first non prime number:

   i += 2;
   if(isPrime(i)) {
       count++;
   }

Moving the sqrt calculation outside is one option, another one is to test for the square value like this because a multiplication is not as expensive as the square root calculation:

for(int i = 3; i*i < num ; i+=2)

For testing why it is slow start with printing out the result of every while iteration, so you can if it just gets slower with larger numbers or if it gets stuck somewhere.

You could also try to work with BigInteger and another algorithm, this one takes around 5 seconds on my old PC and it should work fine with larger numbers too.

import java.math.BigInteger;
import java.util.Date;

public class Euler7
{
    public static void main(String[] args)
    {
        System.out.println(new Date());
        BigInteger primesProduct = BigInteger.valueOf(2*3);
        BigInteger primesFound = BigInteger.valueOf(2);
        BigInteger testForPrime = BigInteger.valueOf(3);
        BigInteger limit = BigInteger.valueOf(10001);
        while(primesFound.compareTo(limit)<0)
        {
            testForPrime = testForPrime.add(BigInteger.valueOf(2));
            if(((primesProduct.gcd(testForPrime)).compareTo(BigInteger.ONE))==0)
            {
                primesProduct = primesProduct.multiply(testForPrime);
                primesFound = primesFound.add(BigInteger.ONE);
            }
        }
        System.out.println(new Date());
        System.out.println("found: "+testForPrime);
    }
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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