ホーム - 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万未満の巡回素数はいくつあるか?

(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)