Problem 35 » 履歴 » リビジョン 2
リビジョン 1 (Noppi, 2024/01/14 05:09) → リビジョン 2/3 (Noppi, 2024/01/14 08:36)
[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]
# [[Problem 35]]
## Circular Primes
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未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である.
100万未満の巡回素数はいくつあるか?
```scheme
(import (scheme base)
(gauche base)
(math prime)
(scheme list))
(define temp-primes (primes))
(define (number-of-digit n)
(assume (exact-integer? n))
(assume (<= 0 n 99_9999))
(cond
[(<= 0 n 9) 1]
[(<= 10 n 99) 2]
[(<= 100 n 999) 3]
[(<= 1000 n 9999) 4]
[(<= 1_0000 n 9_9999) 5]
[(<= 10_0000 n 99_9999) 6]))
;(if (zero? n)
; 1
; (+ (floor->exact (fllog10 n))
; 1)))
(define (ml&eml n)
(assume (exact-integer? n))
(assume (<= 0 n))
(let* ([dn (number-of-digit n)]
[module-num (expt 10
(- dn 1))]
[ml (div n module-num)]
[eml (mod n module-num)])
(values ml eml)))
(define (circular-digits n)
(assume (exact-integer? n))
(assume (<= 0 n))
(if (< n 10)
`(,n)
(let loop ([num n] [result `(,n)])
(let-values ([(ml-num eml-num) (ml&eml num)])
(if (< eml-num
(expt 10
(- (number-of-digit n) 2)))
'()
(let ([next (+ (* eml-num 10)
ml-num)])
(if (find (cut = next <>)
result)
(reverse result)
(loop next (cons next result)))))))))
(define (circular-prime? n)
(let ([cd (circular-digits n)])
(and (not (null? cd))
(every prime? cd))))
(define (prime? n)
(= (car
(drop-while (cut < <> n)
temp-primes))
n))
(define (primes-list n)
(take-while (cut <= <> n) temp-primes))
(define answer-35
(length (filter circular-prime?
(primes-list 99_9999))))
(format #t "35: ~d~%" answer-35)
```