HOME SUMMARY

Problem 35

1. Problem

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 的圆周素数有十三个:2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 和 97。

小于一百万的圆周素数有多少个?

2. Solution

由于轮换的特性,满足条件的素数只能含有 1,3,7 和 9,因为以其他数字作为尾数将必定得到合数。最大的小于 1000000 的数是 999999,总共有 6 位,使用 {1,3,7,9} 组合得到的非个位数共有 46 + 45 + 44 + 43 + 42 = 5456 个,非常少。

自然,使用筛法筛出一百万以下的素数再逐个检查是一种不错的方法,但这里我懒得写筛法了,直接从这 5000 多个数字中使用朴素方法得到素数存到表里面,然后一个一个轮转检查。

(defun eu7-isprime (n)
  (cond
   ((<= n 1) nil)
   ((< n 4) t)
   ((zerop (% n 2)) nil)
   ((< n 9) t)
   ((zerop (% n 3)) nil)
   (t (let ((bound (floor (sqrt n))))
        (named-let f ((i 5))
          (cond
           ((> i bound) t)
           ((zerop (% n i)) nil)
           ((zerop (% n (+ i 2))) nil)
           (t (f (+ i 6)))))))))

下面是和本题相关的代码:

(defun eu35-gen (n ls)
  (cond
   ((= n 0) '(()))
   (t (let ((res (eu35-gen (1- n) ls)))
        (cl-loop
         for a in ls
         append (mapcar (lambda (x) (cons a x))
                        res))))))

(setq eu35-numls
      (let ((ls '(1 3 7 9)))
        (append (eu35-gen 2 ls)
                (eu35-gen 3 ls)
                (eu35-gen 4 ls)
                (eu35-gen 5 ls)
                (eu35-gen 6 ls))))

(setq eu35-nums
      (mapcar (lambda (x)
                (string-to-number
                 (mapconcat
                  (lambda (a)
                    (string (+ a ?0)))
                  x)))
              eu35-numls))

(setq eu35-primes
      (cl-remove-if-not
       'eu7-isprime
       eu35-nums))

(defun eu35-change (n)
  (let ((last (% n 10))
        (n1 (/ n 10))
        (l (floor (log n 10))))
    (+ (* last (expt 10 l)) n1)))

(let ((cnt 0))
  (cl-loop
   for i in eu35-primes
   do (let ((it (eu35-change i)))
        (while (and (/= i it)
                    (member it eu35-primes))
          (setq it (eu35-change it)))
        (when (= i it)
          (cl-incf cnt))))
  cnt)
=> 51
(+ 51 (length '(2 3 5 7)))
=> 55