Euler Solution 35

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 35

How many prime numbers n are there below 1 million where all lexicographical rotations of n are also prime?

Haskell by SanguineV

Runtime: 5.324 seconds (on aglaope)

{- Generate the prime numbers lazily -}
primes :: [Integer]
primes = 2:3:primes'
  where
    1:p:candidates  = [6*k+r | k <- [0..], r <- [1,5]]
    primes'        = p : filter isPrime candidates
    isPrime n       = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p     = n `mod` p == 0

{- Determine how many digits there are for arbitrarily large integers -}
digs :: Integer -> Integer
digs n | n < 10 = 1
digs n = 1 + (digs (div n 10))

{- Return the first digit of an arbitrarily large number -}
firstDig :: Integer -> Integer
firstDig n | n < 10 = n
firstDig n = firstDig (div n 10)

{- Raise a number to a power for arbitrarily large integers -}
pow :: Integer -> Integer -> Integer
pow n 0 = 1
pow n 1 = n
pow n p = n * (pow n (p - 1))

{- Return the rotations of a number, not including the first one -}
rots :: Integer -> [Integer]
rots n = inner dn (pow 10 (dn -1)) n
  where
    dn = digs n
    inner :: Integer -> Integer -> Integer -> [Integer]
    inner 1 md n = []
    inner acc md n = [ 10 * (mod n md) + firstDig n] ++ 
                    (inner (acc - 1) md ( 10 * (mod n md) + firstDig n))

{- Return true if all the digits of the arbitrarily large integer are odd -}
oddDigs :: Integer -> Bool
oddDigs n | n < 10 = mod n 2 == 1
oddDigs n = mod (mod n 10) 2 == 1 && (oddDigs (div n 10))

{- Return true if an integer is an element of a list of integers.
 - Note: assumes the list is sorted! -}
elem' :: Integer -> [Integer] -> Bool
elem' n [] = False
elem' n (x:xs) | x == n = True
elem' n (x:xs) | x > n = False
elem' n (x:xs) = elem' n xs

{- The prime numbers less that 1 million that contain only odd digits.
 - Note: Can filter for odd digits as lexicographical rotations will be even
 -       and hence not prime. -}
p21m = filter oddDigs (takeWhile (< 1000000) primes)

{- Run through the potential primes and for each one see if the rotations are also
 - primes. Add one to the result to account for "2". -}
main = print (1 + length (filter (\x -> foldl (\a b -> a && (elem' b p21m)) True (rots x)) p21m))


Python by Althalus

Runtime: 1.2 seconds

import time
import math
start_time=time.time() 

#Read in from a long list of Primes I generated for an earlier problem (Why re-generate primes every second problem?)
#Limit the primes list to those below 1000000, and with no even digits in them.
#(Sooner or later during the rotation, one of those digits will be on the end, creating something divisible by 2: IE
#NO prime with an even digit can have all rotations prime.)
file = open(r'primes.txt','r')
primes = [int(i) for i in file.readlines() if int(i) < 1000000 and len(set(i).intersection(set('24680'))) == 0]
file.close()

def isCircularPrime(n):
        n = str(n)
        for i in range(1,len(n)):
                if int(n[i:]+n[0:i]) not in primes:
                        return False
        return True

#The rule that limits my primes unfortunately rips the number 2 out of my list of primes. As 2 IS a prime,
#and is a circular prime, let's just startour count at 1, for the circular prime that got prematurely axed.
count=1
for p in primes:
        if isCircularPrime(p):
                print p
                count+=1
print count
run_time = time.time() - start_time
print run_time
Personal tools