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