extra/project-euler/035/035.factor

   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 ;
   5 IN: project-euler.035
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=35
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! The number, 197, is called a circular prime because all rotations of the
  13 ! digits: 197, 971, and 719, are themselves prime.
  14
  15 ! There are thirteen such primes below 100:
  16 !     2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
  17
  18 ! How many circular primes are there below one million?
  19
  20
  21 ! SOLUTION
  22 ! --------
  23
  24 <PRIVATE
  25
  26 : source-035 ( -- seq )
  27     1000000 primes-upto [ number>digits ] map ;
  28
  29 : possible? ( seq -- ? )
  30     dup length 1 > [
  31         dup { 0 2 4 5 6 8 } diff =
  32     ] [
  33         drop t
  34     ] if ;
  35
  36 : rotate ( seq n -- seq )
  37     cut* prepend ;
  38
  39 : (circular?) ( seq n -- ? )
  40     dup 0 > [
  41         2dup rotate 10 digits>integer
  42         prime? [ 1 - (circular?) ] [ 2drop f ] if
  43     ] [
  44         2drop t
  45     ] if ;
  46
  47 : circular? ( seq -- ? )
  48     dup length 1 - (circular?) ;
  49
  50 PRIVATE>
  51
  52 : euler035 ( -- answer )
  53     source-035 [ possible? ] filter [ circular? ] count ;
  54
  55 ! [ euler035 ] 100 ave-time
  56 ! 538 ms ave run time - 17.16 SD (100 trials)
  57
  58 ! TODO: try using bit arrays or other methods outlined here:
  59 !     http://home.comcast.net/~babdulbaki/Circular_Primes.html
  60
  61 SOLUTION: euler035