Problem 7: 10001st prime

*Difficulty: Easy

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?

How to solve:

There are many ways to solve this problem, here are my two methods.

Method 1: Using sieve Eratosthenes to create a prime numbers dictionary , and count to the 10001st prime, print it out.

Method 2: Start from 2, using a helping function to check if a number is prime (There are many possible algorithms to check prime number as well, but here I’m using naive primality test – https://en.wikipedia.org/wiki/Primality_test) and a variable , for example called countPrimes to count how many prime numbers we’ve discovered. Every time we got a new prime number, we increase countPrime to 1, and repeat the process until countPrime reach 10001.

Both methods took <10ms

Implementation (Java)

import java.util.Arrays;

public class Prob7 {

        private static boolean[] sieveEratosthenes;

        public static void main(String[] args) {

                long cur = System.currentTimeMillis();

                sieveEratosthenes= new boolean[110000];

                Arrays.fill(sieveEratosthenes, true);

                for(int i = 2; i <= (int)Math.sqrt(sieveEratosthenes.length); ++i) {

                        if(sieveEratosthenes[i]) {

                                for(int j = i*2; j < sieveEratosthenes.length; j+=i)

                                        sieveEratosthenes[j] = false;

                        }

                 } 

                 int countPrimes = 0;

                 for(int i = 2; i < sieveEratosthenes.length; ++i) {

                           if(sieveEratosthenes[i]) ++countPrimes;

                           if(countPrimes == 10001) {

                                   System.out.println(i);

                                   System.out.println(“Took “ + (System.currentTimeMillis()cur) +”                                      ms”);

                                   break;

                           }

                  }

                  //brute force

                 /*

                 int countPrimes = 1;

                 int n = 3;

                 while(true) {

                         if(isPrime(n))

                                ++countPrimes;

                         if(countPrimes == 10001) {

                                 System.out.println(n);

                                 System.out.println(“Took ” + (System.currentTimeMillis()-cur) + ”                                      ms“);

                                 break;

                         }

                         n+=2;

                 }

                */

        }

         private static boolean isPrime(int n) {

                   if(n <= 1) return false;

                   else if(n <= 3)  return true;

                   else if(n % 2 == 0 || n % 3 == 0return false;

                   int i = 5;

                   while(i*i <= n) {

                           if(n%i == 0 || n%(i+2) == 0)

                                   return false;

                           i += 6;

                   }

                   return true;

         }

}

Advertisements