Project Euler 7: 10,001st Prime Number
Peter Prevos |
483 words | 3 minutes
Share this content
Project Euler 7 delves into the wonderful world of prime numbers. These numbers are interesting because they don't follow a predictable pattern. There is no algorithm to calculate primes, which is what makes them valuable in cryptography.
As the numbers get larger, the gaps between consecutive primes also increase. There are, however, some interesting patterns. There seem to be infinitely many twin primes, which are prime numbers that with a difference of two, such as (3, 5), (5, 7) and (11, 13). Another pattern in prime numbers are sexy primes, which differ by six: e.g. (5,11), (7, 13) and (11, 17). They are called sexy not because these primes are particularly attractive but because of the Latin word for six.
Project Euler 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
Finding the nth prime number can only be solved using brute force because primes do not follow a predictable pattern. We don't have to check whether a number is divisible by any number between 1 and itself. We only have to check whether a number is divisible by all primes between 2 and its square root. 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 Eratosthenes used in Euler Problem 3 generates the prime numbers. The next step cycles through all odd numbers and increments a counter when we find a prime, stopping at 10001.
## Project Euler 7: 10,0001st Prime Number
source("problem003.R", echo = FALSE)
is.prime <- function(n) {
if (n <= 1) return(FALSE)
if (n == 2) return(TRUE)
primes <- esieve(ceiling(sqrt(n)))
return(prod(n %% primes != 0) == 1)
}
answer <- 1
n <- 1 # Start counter
while (n < 10001) { # Find 10001 prime numbers
answer <- answer + 2 # Next number
if(is.prime(answer)) {
n <- n + 1 # Increment counter
}
}
print(answer)Sexy Primes
The largest gap between two primes for the first 10,001 is 72. Sexy primes with a gap of 6 are the most common, as shown in the figure below.
## Sexy Primes
library(ggplot2)
library(dplyr)
primes <- esieve(answer)
p <- length(primes)
gaps <- tibble(Gap = primes[2:p] - primes[1:(p - 1)],
Sexy = Gap %% 6 == 0) %>%
count(Gap, Sexy)
ggplot(gaps, aes(factor(Gap), n, fill = Sexy)) +
geom_col() +
scale_fill_manual(values = c( "#7391AB", "#A62102"), name = "Sexy Prime Gap") +
theme_minimal(base_size = 10) +
labs(title = "Frequency of prime gaps for the first 10,000 primes",
x = "Prime Gap",
y = "Frequency")
guide_legend(title = "Sexy Primes")
ggsave("images/problem-007.png", width = 6, height = 4)Share this content
