Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(Replace `for r` loop with `repeat` loop, since `r` is not used in loop body.) |
(→{{header|Commodore BASIC}}: Add implementation.) |
||
Line 998: | Line 998: | ||
(deterministic-test 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153)) |
(deterministic-test 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153)) |
||
</pre> |
</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}}== |
=={{header|Common Lisp}}== |