**Circular primes**

**Problem 35**

The number, 197, is called 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.

How many circular primes are there below one million?

The approach which I thought of was to find all the prime numbers below million, apply circular shift on them, check if those are prime as well and then include them in the list of circular primes.

I had thought I had already written a function to get all the prime numbers under `n`

before. After going through all the previous codes I could not find it anywhere so decided to write one myself. At first I thought of using the `is_prime`

function from Problem 3 for every odd number but this was very much time consuming for million numbers. Then after searching extensively for fastest way to get prime numbers under `n`

I got directed to Sieve of Eratosthenes.

The concept for Sieve of Eratosthenes is you have an array of numbers from 1 to `n`

. 2 is a prime number and then remove all the numbers which are multiples of 2 under `n`

. Then take next number which is 3, 3 is prime and remove all the numbers which are multiple of 3. Now, 4 is already cancelled from the previous instance of 2. We move to 5, 5 is prime and remove all the multiples of 5 under `n`

and we continue this till we reach end of the list. So you basically take the current first element in the list, add it in the prime number list and remove its multiples from the list. No need to do any additional check if it is prime or not because if the number is not prime it would definitely be a multiple of some other number from the past numbers which we have already encountered and would cancel it out.

get_primes_under_n = function (n) {
num_seq = seq(3, n, 2)
prime_number = numeric()
while(length(num_seq) >= 1) {
prime_number = c(prime_number, num_seq[1])
num_seq = setdiff(num_seq, seq(num_seq[1], n, num_seq[1]))
}
return(c(2, prime_number))
}

I wrote this function for Sieve of Eratosthenes which takes up most of the computing time in the function. Moving forward, we now have all the prime numbers under `n`

, now for each prime we need to check if its circular rotations are prime as well. At first, I was confused here. I thought we have to check for each possible combination of those numbers. So for eg : For 123, we need to check for 123, 231, 312, 132, 213 and 321 which wasn’t true. We just need to check for circular rotations which includes 123, 231 and 312.

Unfortunately, in R we do not have a function as of now which will do this circular shifting directly. (Although, I think it is proposed in next release of `data.table`

somewhere). Anyway, Jaap from SO helped me to write a function which does this circular shift which I later modified a little according to my requirement.

cyc_shift = function(x) {
if(length(x) == 1) return(x)
comb = paste0(x, collapse = "")
n <- nchar(comb) - 1
c(comb, lapply(1:n, function(i) paste0(c(tail(x,-i),
head(x,i)), collapse = "")))
}

This basically takes a character array and circular shifts it and sends the output. So basically consider this –

split_num
#[1] "1" "2" "1" "3"
cyc_shift(split_num)
#[[1]]
#[1] "1213"
#[[2]]
#[1] "2131"
#[[3]]
#[1] "1312"
#[[4]]
#[1] "3121"

Before sending the prime number to circular shift function we check if it contains any of the even number `c(0, 2, 4, 6, 8)`

because if it does then it cannot be circular prime as when we circular shift the numbers that number would atleast be once in the units place which would make it divisible by 2 and eventually it would be rejected. After the number has passed this test, we pass it to `cyc_shift`

function to get all the circular shifted arrays and we check if they all are prime as well. As we had precalulated the prime numbers under `n`

already we can check if all these circular shifted numbers are present in that array.

count_circular_primes = function(num) {
prime_numbers = get_primes_under_n(num)
final_answer = numeric()
for(i in prime_numbers) {
split_num = strsplit(as.character(i), "")[[1]]
#If it contains any of the even digit then it is going to be divisible by 2 in #any one of the circular shift operation
if (any(split_num %in% c("0","2","4","6","8")) & length(split_num) > 1)
next
all_nums = as.numeric(cyc_shift(split_num))
#All possible variations should be prime numbers, hence should be included in #the prime numbers we had calculated previously
if (all(all_nums %in% prime_numbers))
final_answer = c(final_answer, i)
}
return(length(final_answer))
}

You can see the entire code on Github.