Euler Problem 35 takes us back to the world of prime numbers, in particular circular primes. The Online Encyclopedia of Integers (A068652) lists the fist 46 numbers for which every cyclic permutation is a prime.
The number 197 is a 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.
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:
esieve: Generate primesis_prime: Checks whether a number is primerotate_left: Rotates the a number # Sieve of Eratosthenes
esieve <- 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)
}
## Check if a number is prime
is_prime <- function(x) {
if (x <= 1) return(FALSE)
if (x == 2 | x == 3) return(TRUE)
primes <- esieve(ceiling(sqrt(x)))
return(all(x %% primes != 0))
}
## Rotate a number to the left
rotate_left <- function(x) {
if (x <= 9) return(x)
i <- 1
y <- vector()
while(x >= 1) {
d <- x %% 10
y[i] <- d
i <- i + 1
x = x %/% 10
}
as.numeric(paste(y[c((length(y) - 1):1, length(y))], collapse = ""))
}
## Check circularity
is_circular_prime <- function(x) {
n <- trunc(log10(x)) + 1
p <- vector(length = n)
for (r in 1:n) {
p[r] <- is_prime(x)
x <- rotate_left(x)
}
all(p)
}
primes <- esieve(1E6)
length(which(sapply(primes, is_circular_prime)))
The main program runs through each of the 78,498 primes below one million, saves their digits in a vector and then cycles the numbers to test for primality of each rotation.