Solutions to Project Euler 35: How many circular primes are there below one million? Solution in the R language for statistical computing

Project Euler 35: Circular Primes below One Million

Peter Prevos

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.

How many circular primes are there below one million?

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 primes
  • is_prime: Checks whether a number is prime
  • rotate_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

You might also enjoy reading these articles

Project Euler 144: Laser Beams and Elliptical Billiards

Project Euler 33: Digit Cancelling Fractions

Project Euler 32: Pandigital Products