problem 35 - mtsuyuguの日記

1,000,000 以下の素数の中で桁を回転させてできる数字がすべて素数(ex. 197, 719, 971) である数はいくつあるかという問題です。

primes.txt にはリストの形で 1,000,000 以下の素数が列挙しています。添え字が素数の要素は値が 1 の 1,000,000 要素からなるベクタを生成して素数のチェックを行っています。

(use srfi-1)
(use srfi-13)

(define (read-primes fn)
  (let* ((in (open-input-file fn))
         (primes (read in)))
    (close-input-port in)
    primes))

(define primes (read-primes "primes.txt"))
(define v (let1 v (make-vector 1000000 0)
                (for-each (lambda (x)
                            (vector-set! v x 1)) primes)
                v))

; 197 -> '(197 971 719)
(define (circular-number num)
  (let* ((strnum (x->string num))
         (len (string-length strnum)))
    (delete-duplicates
      (map (lambda (n)
             (x->integer (string-append (string-drop strnum n)
                                        (string-take strnum n))))
           (iota len)))))

(define (all-primes? nlist)
  (every (lambda (x) (= (vector-ref v x) 1)) nlist))

(define (p35)
  (length (fold (lambda (x y)
                  (if (all-primes? (circular-number x))
                    (cons x y)
                    y)) '() primes)))

(print (p35))