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。
小于一百万的圆周素数有多少个?
由于轮换的特性,满足条件的素数只能含有 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