## 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;

}

}