Circular primes: Difference between revisions
PicoLisp version
SqrtNegInf (talk | contribs) m (→{{header|Raku}}: note use of 'ntheory' module) |
(PicoLisp version) |
||
Line 1,986:
</pre>
=={{header|PicoLisp}}==
For small primes, I only check numbers that are made up of the digits 1, 3, 7, and 9, and I also use a small prime checker to avoid the overhead of the Miller-Rabin Primality Test. For the large repunits, one can use the code from the Miller Rabin task.
<lang PicoLisp>
(load "plcommon/primality.l") # see task: "Miller-Rabin Primality Test"
(de candidates (Limit)
(let Q (0)
(nth
(sort
(make
(while Q
(let A (pop 'Q)
(when (< A Limit)
(link A)
(setq Q
(cons
(+ (* 10 A) 1)
(cons
(+ (* 10 A) 3)
(cons
(+ (* 10 A) 7)
(cons (+ (* 10 A) 9) Q))))))))))
6)))
(de circular? (P0)
(and
(small-prime? P0)
(fully '((P) (and (>= P P0) (small-prime? P))) (rotations P0))))
(de rotate (L)
(let ((X . Xs) L)
(append Xs (list X))))
(de rotations (N)
(let L (chop N)
(mapcar
format
(make
(do (dec (length L))
(link (setq L (rotate L))))))))
(de small-prime? (N) # For small prime candidates only
(if (< N 2)
NIL
(let W (1 2 2 . (4 2 4 2 4 6 2 6 .))
(for (D 2 T (+ D (pop 'W)))
(T (> (* D D) N) T)
(T (=0 (% N D)) NIL)))))
(de repunit-primes (N)
(let (Test 111111 Remaining N K 6)
(make
(until (=0 Remaining)
(setq Test (inc (* 10 Test)))
(inc 'K)
(when (prime? Test)
(link K)
(dec 'Remaining))))))
(setq Circular
(conc
(copy (2 3 5 7))
(filter circular? (candidates 1000000))
(mapcar '((X) (list 'R X)) (repunit-primes 4))))
(prinl "The first few circular primes:")
(println Circular)
(bye)
</lang>
{{Out}}
<pre>
The first few circular primes:
(2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939 199933 (R 19) (R 23) (R 317) (R 1031))
</pre>
=={{header|Prolog}}==
Uses a miller-rabin primality tester that I wrote which includes a trial division pass for small prime factors. One could substitute with e.g. the Miller Rabin Primaliy Test task.
| |||