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?
197は循環素数?と呼ばれる。197,971,719と、ぐるっと回しても、ぜーんぶ素数だからだ。
100以下では2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97の13個がある。
100万以下の循環素数は何個ある?
循環素数と呼ばれてるのかどうかは知らない(汗
今まで作ってきたユーティリティを総動員で解いてみる。
(define (split-map f l) (letrec ((iter (lambda (acc l) (if (null? l) '() (cons (f acc l) (iter (cons (car l) acc) (cdr l))))))) (iter '() l))) (define (number->list n . base) (letrec ((b (if (null? base) 10 (car base))) (iter (lambda (acc n) (let ((q (quotient n b)) (m (cons (modulo n b) acc))) (if (zero? q) m (iter m q)))))) (iter '() n))) (define (list->number l) (letrec ((iter (lambda (l cont) (if (null? l) (cont 0 0) (iter (cdr l) (lambda (sum k) (cont (+ (* (car l) (expt 10 k)) sum) (+ k 1)))))))) (iter l (lambda (sum k) sum)))) (define (k n) (inexact->exact (floor (/ (log n) (log 10))))) (define (prime? n) (define (trial-divisor t) (or (< n (* t t)) (and (not (zero? (remainder n t))) (trial-divisor (+ t 2))))) (if (even? n) (= n 2) (trial-divisor 3)))
- split-map
- 分割map。新登場。
- 前のリストが逆順になっちゃうんだよね。
- number->list,list->number
- 1234 <-> (1 2 3 4)とする。
- k
- 桁数。新登場。
- prime?
- 試し割の素数判定
というユーティリティ達を使って、
素数リストを作って > 数字を分解 > 循環したリストを作る > 数字に戻す > 素数判定 > 全部生き残ったら > リストに追加 > いくつあるかな?
という流れ。
(length (fold-right (lambda (x acc) (if (= (k (- x 1)) (length (filter prime? (cdr (map (lambda (l) (list->number l)) (split-map (lambda (f b) (append b (reverse f))) (number->list x))))))) (cons x acc) acc)) '() (filter prime? (iota (- 1000000 1) 2)))) ; 55
うは。
同じ計算を何度もしてる所があるので、なんとかしたい所。