Site icon R-bloggers

Euler Problem 7: 10,001st Prime

[This article was first published on Data Science with R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Euler Problem 7 Definition

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 1,0001st prime number?

Solution

The is.prime function determines whether a number is a prime number by checking that it is not divisible by any prime number up to the square root of the number.

The Sieve of used in Euler Problem 3 can be reused to generate prime numbers.

This problem can only be solved using brute force because prime gaps (sequence A001223 in the OEIS) do not follow a predictable pattern.

is.prime <- function(n) {
    primes <- esieve(ceiling(sqrt(n)))
    prod(n%%primes!=0)==1
}

i <- 2 # First Prime
n <- 1 # Start counter
while (n<10001) { # Find 10001 prime numbers
    i <- i + 1 # Next number
    if(is.prime(i)) { # Test next number
        n <- n + 1 # Increment counter
        i <- i + 1 # Next prime is at least two away
    }
}

answer <- i-1

The largest prime gap for the first 10,001 primes is 72. Sexy primes with a gap of 6 are the most common and there are 1270 twin primes.

Prime gap frequency distribution for the first 10001 primes.

The post Euler Problem 7: 10,001st Prime appeared first on Data Science with R.

To leave a comment for the author, please follow the link and comment on their blog: Data Science with R.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.