Project Euler Problem 7: 10001st prime

Problem

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?

Solution

Some optimization includes

• Use an array to store found prime numbers to check future prime number candidate
• Only check numbers 6k+1 and 6k-1, because we know other number can either be divided by 2 or 3.

      private static final int NUMBER = 10001;  
      private static final long[] primeNumbers = new long[NUMBER-1];  
      public static void main(String[] args) {  
           primeNumbers[0]=3L;  
           int index = 1;  
           for (int i=6; index < NUMBER - 1; i+=6){ //Because we start at 3 instead of 2  
                for (int j=-1; j <= 1; j+=2){ //Only test 6K+1 and 6k-1  
                     if (isPrimeNumber(i+j, index)){  
                          primeNumbers[index]=i+j;  
                          index++;  
                     }  
                     if (index >= NUMBER - 1){  
                          break;  
                     }  
                }  
           }       
           System.out.println(primeNumbers[index-1]);  
      }  
      private static boolean isPrimeNumber(long number, int index){  
           double sqrt = Math.sqrt(number);  
           for (int i = 0; primeNumbers[i] <= sqrt; i++){  
                if (number % primeNumbers[i] == 0){  
                     return false;  
                }  
           }  
           return true;  
      }