Project Euler

A Taste of Number Theory

Problem 7: 10,001st Prime

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?

The Catch

How to determine whether an arbitrary number x is prime.

The Light

Reuse the prime checking code in Problem 3 to find the 10,100st prime number.

The Code

public class Problem7
{
  public static void main(String[] args)
  {
    int count = 1; //Start count at 1 because 2 is the first prime number

    for(int i = 3;; i += 2) //Increment by 2 because primes from 3 onward are odd
    {
      if(isPrime(i))
        ++count;
      if(count == 10001)
      {
        System.out.println(i);
        break;
      }
    }
  }

  public static boolean isPrime(int n)
  {
    if(n < 2)
      return false;

    if(n != 2 && n % 2 == 0)
      return false;

    for(int i = 3; i*i <= n; i += 2)
    {
      if(n % i == 0)
        return false;
    } 
    return true;
  }
}