Fermat numbers: Difference between revisions
add PicoLisp
(Added Common Lisp) |
(add PicoLisp) |
||
Line 1,565:
Factors of F12: 114689*910626896...<1,228 digits>...946770433 (last factor is not prime) [0.6s]
Factors of F13: 109074813...<2,467 digits>...715792897 (not prime) [1.3s]
</pre>
=={{header|PicoLisp}}==
<lang PicoLisp>(seed (in "/dev/urandom" (rd 8)))
(de **Mod (X Y N)
(let M 1
(loop
(when (bit? 1 Y)
(setq M (% (* M X) N)) )
(T (=0 (setq Y (>> 1 Y)))
M )
(setq X (% (* X X) N)) ) ) )
(de isprime (N)
(cache '(NIL) N
(if (== N 2)
T
(and
(> N 1)
(bit? 1 N)
(let (Q (dec N) N1 (dec N) K 0 X)
(until (bit? 1 Q)
(setq
Q (>> 1 Q)
K (inc K) ) )
(catch 'composite
(do 16
(loop
(setq X
(**Mod
(rand 2 (min (dec N) 1000000000000))
Q
N ) )
(T (or (=1 X) (= X N1)))
(T
(do K
(setq X (**Mod X 2 N))
(when (=1 X) (throw 'composite))
(T (= X N1) T) ) )
(throw 'composite) ) )
(throw 'composite T) ) ) ) ) ) )
(de gcd (A B)
(until (=0 B)
(let M (% A B)
(setq A B B M) ) )
(abs A) )
(de g (A)
(% (+ (% (* A A) N) C) N) )
(de pollard-brent (N)
(let
(A (dec N)
Y (rand 1 (min A 1000000000000000000))
C (rand 1 (min A 1000000000000000000))
M (rand 1 (min A 1000000000000000000))
G 1
R 1
Q 1 )
(ifn (bit? 1 N)
2
(loop
(NIL (=1 G))
(setq X Y)
(do R
(setq Y (g Y)) )
(zero K)
(loop
(NIL (and (> R K) (=1 G)))
(setq YS Y)
(do (min M (- R K))
(setq
Y (g Y)
Q (% (* Q (abs (- X Y))) N) ) )
(setq
G (gcd Q N)
K (+ K M) )
)
(setq R (* R 2)) )
(when (== G N)
(loop
(NIL (> G 1))
(setq
YS (g YS)
G (gcd (abs (- X YS)) N) ) ) )
(if (== G N)
NIL
G ) ) ) )
(de factors (N)
(sort
(make
(loop
(setq N (/ N (link (pollard-brent N))))
(T (isprime N)) )
(link N) ) ) )
(de fermat (N)
(inc (** 2 (** 2 N))) )
(for (N 0 (>= 8 N) (inc N))
(println N ': (fermat N)) )
(prinl)
(for (N 0 (>= 8 N) (inc N))
(let N (fermat N)
(println
N
':
(if (isprime N) 'PRIME (factors N)) ) ) )</lang>
{{out}}
<pre>
$ pil VU.l
0 : 3
1 : 5
2 : 17
3 : 257
4 : 65537
5 : 4294967297
6 : 18446744073709551617
7 : 340282366920938463463374607431768211457
8 : 115792089237316195423570985008687907853269984665640564039457584007913129639937
3 : PRIME
5 : PRIME
17 : PRIME
257 : PRIME
65537 : PRIME
4294967297 : (641 6700417)
18446744073709551617 : (274177 67280421310721)
340282366920938463463374607431768211457 : (59649589127497217 5704689200685129054721)
115792089237316195423570985008687907853269984665640564039457584007913129639937 : (1238926361552897 93461639715357977769163558199606896584051237541638188580280321)
</pre>
| |||