Project Euler 35: Circular Primes below One Million
Peter Prevos |
390 words | 2 minutes
Share this content
Euler Problem 35 takes us back to the world of prime numbers, in particular circular primes. The Online Encyclopedia of Integers (A068652) lists the first 46 decimal numbers for which every cyclic permutation is a prime.
Project Euler 35 Definition
The number 197 is a decimal circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
Proposed Solution in R
This code reuses the function that strips all digits for a number, presented in Euler Problem 30. The solution for this problem also use the is_prime function to test whether a number is a prime, developed for Euler Problem 7.
The following auxiliary functions help to solve the problem:
prime_sieve: Generate primesis_prime: Checks whether a number is primerotate_left: Rotates the a number
The is_circular_prime function first removes any numbers greater than 9 that contains either a 0, 2, 4, 5, 6 or 8, as at least one rotation will be divisible by either 2 or 5, which drastically reduces the search space.
The main program tests each of the 78,498 primes below one million and counts the number of circular ones.
prime_sieve <- function(x) {
if (x == 1) return(NULL)
if (x == 2) return(n)
l <- 2:x
i <- 1
p <- 2
while (p^2 <= x) {
l <- l[l == p | l %% p!= 0]
i <- i + 1
p <- l[i]
}
return(l)
}
is_prime <- function(x) {
if (x <= 1) return(FALSE)
if (x == 2 | x == 3) return(TRUE)
primes <- prime_sieve(ceiling(sqrt(x)))
return(all(x %% primes != 0))
}
x <- 101
rotate_left <- function(x) {
if (x < 10) return(x)
n <- floor(log10(x)) + 1
first_digit <- x %/% 10^(n - 1)
rest <- x %% 10^(n - 1)
rotated <- rest * 10 + first_digit
return(rotated)
}
is_circular_prime <- function(x) {
if (x > 9 & any(grepl("[024568]", as.character(x)))) return(FALSE)
n <- floor(log10(x)) + 1
p <- vector(length = n)
for (r in 1:n) {
p[r] <- is_prime(x)
if (!p[r] ) return(FALSE)
x <- rotate_left(x)
}
return(TRUE)
}
primes <- prime_sieve(1E6)
system.time({
circular_primes <- primes[sapply(primes, is_circular_prime)]
print(length(circular_primes))
})Share this content
