Project Euler

[ホーム](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)

```