1 ! Copyright (c) 2008 Aaron Schaefer.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: kernel math math.combinatorics math.parser math.primes
4 project-euler.common sequences sets ;
7 ! http://projecteuler.net/index.php?section=problems&id=35
12 ! The number, 197, is called a circular prime because all rotations of the
13 ! digits: 197, 971, and 719, are themselves prime.
15 ! There are thirteen such primes below 100:
16 ! 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
18 ! How many circular primes are there below one million?
26 : source-035 ( -- seq )
27 1000000 primes-upto [ number>digits ] map ;
29 : possible? ( seq -- ? )
31 dup { 0 2 4 5 6 8 } diff =
36 : rotate ( seq n -- seq )
39 : (circular?) ( seq n -- ? )
41 2dup rotate 10 digits>integer
42 prime? [ 1- (circular?) ] [ 2drop f ] if
47 : circular? ( seq -- ? )
48 dup length 1- (circular?) ;
52 : euler035 ( -- answer )
53 source-035 [ possible? ] filter [ circular? ] count ;
55 ! [ euler035 ] 100 ave-time
56 ! 538 ms ave run time - 17.16 SD (100 trials)
58 ! TODO: try using bit arrays or other methods outlined here:
59 ! http://home.comcast.net/~babdulbaki/Circular_Primes.html