7

Project-Euler / 7

What is the 10 001^st prime number?

Here’s my solution in Java:

import static java.lang.Math.sqrt;

public class Problem7 {
    public static void main(String[] args) {
        int count = 0;
        int div = 1;
        int result = 1;
        while (count < 10_001) {
            result++;
            for (div=(int)sqrt(result); div>0; div--)
                if (result % div == 0) break;
            if (div == 1) count++;
        }
        System.out.println(result);
    }
}

The only thing to note is I’m dividing from \(\lfloor\sqrt n\rfloor\) (and down to 1) to check if \(n\) is prime. The reason I don’t need to check more than that is if \(d\) is a divisor of \(n\) then \(\tfrac{n}{d}\) is also a divisor of \(n\). This substantially speeds up the program.