Euler Problem 7: 10001st prime

Oct 21, 2017 15:55 · 409 words · 2 minutes read R Python Project_Euler

Mathedemo

You might ask why I skip Euler Problem 6. It’s because Euler Problem 6 is so easy that I don’t want to write a blog about its solution. In this post, we will discuss Euler Problem 7.

Euler 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 10001st prime number?

Solution

To generalize this problem, we can ask “What is the \(N^{th}\) prime number?”. In Euler Problem 3, we built all_primes() function to find out how many prime numbers less than or equal to a given number. We, however, cannot use this function to find out the target prime because we don’t know which number is bigger than the target.

My strategy is following:

1.Create a list primes to save each prime.

2.primes is initialized with first prime.

3.Check if the length of primes is less than number \(N\). If so, do step 4 and 5.

4.Start with 3 and loop through odd numbers. Check if it’s a prime by the helper function is_prime().

5.Add the number to primes if is_prime() returns true.

6.Loop stops if the length of primes equal to \(N\).

Solution in R

is_prime <- function(n) {
  if (n == 3) {
    return(TRUE)
  }
  
  if (n %% 2 == 0) {  # Even numbers bigger than 2 are no primes
    return(FALSE)
  }
  
  for (i in seq(3, n ^ 0.5 + 1, 2)) {  # Only loop through odd numbers
    if (n %% i == 0) {
      return(FALSE)
    }
  }
  
  return(TRUE)
}


get_prime2 <- function(x) {
  primes <- c(2)
  m <- 3
  
  while (length(primes) < x) {  # Loop until we get x amount of primes
    if (is_prime(m)) {
      primes <- c(primes, m)
    }
    
    m <- m + 2  # Only loop through odd numbers
  }
  
  primes[length(primes)]
}


get_prime2(10001)

## [1] 104743

Solution in Python

def is_prime(n):
    if n == 3:
        return True

    if n % 2 == 0:  # Even numbers bigger than 2 are no primes
        return False

    for i in range(3, int(n ** 0.5) + 1, 2):  # Only loop through odd numbers
        if n % i == 0:
            return False

    return True


def get_prime(x):
    primes = [2]
    m = 3

    while len(primes) < x:  # Loop until we get x amount of primes
        if is_prime(m):
            primes.append(m)
        m += 2  # Only loop through odd numbers

    print(primes[-1])


get_prime(10001)

## 104743