Problem 007 : 10001st Prime

10001st prime

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?

                                                                                                           https://projecteuler.net/problem=7
Problem 7 is about prime generation.

The efficiency of this problem can differ based on which algorithm we take.

We might want to use sieve for this problem, yet since we don't know the exact limit, we cannot use it (unless it will become more inefficient algorithm).

We will look at the algorithm that determines whether a number is a prime.

public static boolean isPrime(int n)
{
     if (n <= 3) return n > 1;
     else if (n % 2 == 0 || n % 3 == 0) return false;
     else
     {
      for (int i = 5, end = (int)Math.sqrt(n); i <= end; i += 6)
      {
       if (n % i == 0 || n % (i + 2) == 0) return false;
      }
     }
     return true;
}

This is by far the most efficient algorithm for checking primality of an integer.

We will use while loop until we reach our target, 10001st prime number.

Quick trick would be an increment of the integer by 2, since all even numbers cannot be prime.

Answer is 104743
Execution time is 8 ms, or 0.008 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem007.java