/* Euler #35 in Picat. 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? """ This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import util. main => go. go => time(euler35). % Using a map: 0.7s euler35 => PrimesMap = new_map([P=1 : P in primes(1000000)]), NumCircularPrimes = 0, foreach(N=_V in PrimesMap) if is_circular_prime2(N,PrimesMap) then NumCircularPrimes := NumCircularPrimes + 1 end end, println(NumCircularPrimes). % 2.54s euler35b => NumCircularPrimes = 0, Primes = primes(1000000), foreach(N in Primes) if is_circular_prime(N) then NumCircularPrimes := NumCircularPrimes + 1 end end, println(NumCircularPrimes). % Note: Running euler35c after euler35b gives % unreliable results since then prime_cached/1 are then cached. % 2.6s euler35c => println([_:P in primes(1000000), is_circular_prime(P)].length). % % check is a number (a prime) is a circular prime % is_circular_prime(P) => S = P.to_string(), Size = S.length, V = P, foreach(I in 2..Size, prime_cached(V)) V := ([S[J] : J in I..Size] ++ [S[J] : J in 1..I-1]).to_integer() end, prime_cached(V). % using a map of the primes instead of via prime_chaced/1 is_circular_prime2(P,PrimeMap) => S = P.to_string(), Size = S.length, V = P, foreach(I in 2..Size, PrimeMap.has_key(V)) V := ([S[J] : J in I..Size] ++ [S[J] : J in 1..I-1]).to_integer() end, PrimeMap.has_key(V). table prime_cached(N) => prime(N).