Miller–Rabin primality test: Difference between revisions
→{{header|Commodore BASIC}}: Add implementation.
(Replace `for r` loop with `repeat` loop, since `r` is not used in loop body.) |
(→{{header|Commodore BASIC}}: Add implementation.) |
||
Line 998:
(deterministic-test 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153))
</pre>
=={{header|Commodore BASIC}}==
<lang basic>100 PRINT CHR$(147)CHR$(18)"**** MILLER-RABIN PRIMALITY TEST ****":PRINT
110 OPEN 1, 0
120 PRINT "ENTER N:";: INPUT#1, N$: PRINT
130 N = VAL(N$): IF N<2 THEN 120
140 IF 0 = (N AND 1) THEN PRINT "(EVEN)": GOTO 400
150 PRINT "ENTER K:";: INPUT#1, K$: PRINT
160 K = VAL(K$): IF K < 1 THEN 150
170 CLOSE 1
180 D = N - 1
190 S=0
200 D = D / 2: S = S + 1
210 IF 0 = (D AND 1) THEN 200
220 P = 1
230 FOR I = 1 TO K
240 : A = INT(RND(.) * (N - 2)) + 2
250 : X = 1
260 : FOR J = 1 TO D
270 : X = X * A
280 : X = X - N * INT(X / N)
290 : NEXT J
300 : IF (X = 1) OR (X = (N - 1)) THEN 380
310 : FOR J = 1 TO S - 1
320 : X = X * X
330 : X = X - N * INT(X / N)
340 : IF X = 1 THEN P = 0: GOTO 390
350 : IF X = N - 1 THEN 380
360 : NEXT J
370 : P = 0:GOTO 390
380 NEXT I
390 P = P * (1 - 1 / (4 * K))
400 IF P THEN PRINT "PROBABLY PRIME (P >="P")": END
410 PRINT "COMPOSITE."</lang>
{{Out}}
Sample runs. Probability of primality is is computed as 1-1/4<sup>k</sup>, based on the fraction of "strong liars" which approaches 1/4 in the limit.
<pre>**** MILLER-RABIN PRIMALITY TEST ****
ENTER N:1747
ENTER K:2
PROBABLY PRIME (P >= .875 )
READY.</pre>
<pre>**** MILLER-RABIN PRIMALITY TEST ****
ENTER N:4353
ENTER K:2
COMPOSITE.
READY.</pre>
(Self-evident, since 4+3+5+3=15 is a multiple of 3.)
=={{header|Common Lisp}}==
| |||