I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Circular Primes

06.06.2013
| 4700 views |
  • submit to reddit

It's Thursday, so it's time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Circular Primes 

circular prime  is a prime number with the property that the number generated at each intermediate step when cyclically permuting its (base 10) digits will be prime. For example 1193 is a circular prime, since 1931, 9311 and 3119 all are also prime. 

Your task is to calculate how many circular primes exist below 1 million. 


Catch up on all our previous puzzlers here

Comments

sun east replied on Thu, 2013/06/06 - 8:45am

A  four lines solution in Scala:

scala> :paste
// Entering paste mode (ctrl-D to finish)

import Stream.{from, iterate}
val pm: Stream[Int] = 2 #:: from(3).filter(n => pm.takeWhile(p => p*p<=n).forall(n%_>0))
val set = pm.takeWhile(_ < 1000000).map(_.toString).toSet
val res = set.filter(n => iterate(n, 6)(x => x.tail :+ x.head).forall(set))
print(res.toSeq.map(_.toInt).sorted)

// Exiting paste mode, now interpreting.

ArrayBuffer(2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991,
1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 19
3939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331)

K Hyland replied on Thu, 2013/06/06 - 9:03am

Verbose Python solution:

Comments and improvements welcome. 

import math

Max = 1000000

def isPrime(num):
	for i in range(int(math.sqrt(num))+1)[1:]:
		if(i>1):
			if(float(num)/float(i)==int(num)/int(i)):
				return False
	return True
			

def getPrimes(max):
	for i in range(max):
		if(i>1):
			if(isPrime(i)):
				yield i
	
def rotations(num):
	strNum = str(num)
	for i in range(len(strNum)):
		yield(int(strNum[i:]+strNum[:i]))
	
def isCircularPrime(num):
	for p in rotations(num):
		if(not isPrime(p)):
			return False
	return True		

primes = getPrimes(Max)
#print str(len(list(getPrimes(Max))))," Primes = "#,list(getPrimes(Max))
cprimes = []
for prime in primes:
	if isCircularPrime(prime):
		cprimes += [prime]
print str(len(cprimes))," cicular primes = ",cprimes
	


Ondřej Smola replied on Mon, 2013/06/17 - 10:18am in response to: K Hyland

Solution using Racket (Scheme). Sorry for indentation but java.dzone does not support Racket as input language, but perl works well ...
(define (cilcular-primes n)
  (filter (lambda(prime)
            (let* ([prime-as-char-list (string->list (~a  prime))]
                   [prime-rotation-test (lambda (pos acc)
                    (and acc (prime? (string->number (list->string 
                     (append (drop prime-as-char-list pos)
                      (take prime-as-char-list pos)))))))])                        
              (foldr prime-rotation-test true
                     (range 1 (length prime-as-char-list)))))                                    
          (filter prime? (range 1 n 2))))

(cilcular-primes (expt 10 6))


Bruce Cox replied on Sat, 2013/06/15 - 10:18am

 @K Hyland

Your method for is finding all the primes is rather slow. You could use the Sieve of Eratosthenes to speed that part up and store the primes in a dict so you can easily test for primality without dividing again by lots of numbers. All numbers ending in 2, 4, 5, 6 or 8 are prime, except 2 and 5, so you could filter out any 2+-digit prime containing any of those numbers (that cuts the primes in consideration from 78000+ to 1113). That's probably not necessary when the primes are already in a dict.

def erato(limit):
    # counting from 1 is easier, so set sieve[0] to None
    # and 1 is not prime, so set sieve[1] to False
    sieve = [None, False] + [True] * (limit - 1)
    isPrime = {}
    for p in range(1, limit + 1):
        # if p is still in the sieve, it is prime
        if sieve[p]:
            isPrime[p] = True
            # remove all the multiples of p from the sieve
            for x in range(2 * p, limit + 1, p):
                sieve[x] = False
    return isPrime

def rotations(num):
	strNum = str(num)
	for i in range(len(strNum)):
		yield(int(strNum[i:]+strNum[:i]))
	
def isCircularPrime(num, isPrime):
	for p in rotations(num):
		if(not p in isPrime):
			return False
	return True

isPrime = erato(1000000)
cprimes = filter(lambda(p): isCircularPrime(p, isPrime), isPrime)

Cheers,

Bruce


Camilo Rivera replied on Thu, 2013/10/31 - 1:05am

Mi contribution in Ruby. Probably needs some tuning but here it goes anyway:

require 'prime'

def rotate(num)
	return [num] if num < 10
	snum = num.to_s
	elems, elem = [], snum
	(snum.length-1).times do |i|
		elem = elem[1..-1] << elem[0]
		elems[i] = elem.to_i
	end
	elems
end

puts (1...1000000).select{ |num| Prime.prime?(num) && rotate(num).all?{ |elem| Prime.prime?(elem) } }

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.