Miller–Rabin primality test: Difference between revisions
m
→{{header|REXX}}
| (2 intermediate revisions by the same user not shown) | |||
Line 6,149:
return Datatype(x,'w')
</syntaxhighlight>
As in the previous version, k = 3 was hard coded and seems good enough for this test. A higher k gives more confidence on the probable primes, but also a longer running time.
This version will produce output (Windows 11, Intel i7, 4.5Ghz, 16G):
<pre>
REXX-ooRexx_5.0.0(MT)_64-bit 6.05 23 Dec 2022
25 numbers of the form 2^n-1, mostly Mersenne primes
Up to about 25 digits deterministic, above probabilistic
2^2-1 = 3 (1 digits) is for sure prime (0.000 seconds)
2^3-1 = 7 (1 digits) is for sure prime (0.000 seconds)
2^5-1 = 31 (2 digits) is for sure prime (0.000 seconds)
2^7-1 = 127 (3 digits) is for sure prime (0.000 seconds)
2^11-1 = 2047 (4 digits) is not prime (0.000 seconds)
2^13-1 = 8191 (4 digits) is for sure prime (0.000 seconds)
2^17-1 = 131071 (6 digits) is for sure prime (0.000 seconds)
2^19-1 = 524287 (6 digits) is for sure prime (0.000 seconds)
2^23-1 = 8388607 (7 digits) is not prime (0.000 seconds)
2^31-1 = 2147483647 (10 digits) is for sure prime (0.000 seconds)
2^61-1 = 2305843009213693951 (19 digits) is for sure prime (0.000 seconds)
2^89-1 = 618970019642...0137449562111 (27 digits) is probable prime (0.016 seconds)
2^97-1 = 158456325028...5187087900671 (30 digits) is not prime (0.000 seconds)
2^107-1 = 162259276829...1578010288127 (33 digits) is probable prime (0.000 seconds)
2^113-1 = 103845937170...0992658440191 (35 digits) is not prime (0.000 seconds)
2^127-1 = 170141183460...3715884105727 (39 digits) is probable prime (0.016 seconds)
2^131-1 = 272225893536...9454145691647 (40 digits) is not prime (0.000 seconds)
2^521-1 = 686479766013...8291115057151 (157 digits) is probable prime (0.453 seconds)
2^607-1 = 531137992816...3219031728127 (183 digits) is probable prime (0.765 seconds)
2^1279-1 = 104079321946...5703168729087 (386 digits) is probable prime (9.407 seconds)
2^2203-1 = 147597991521...7686697771007 (664 digits) is probable prime (36.527 seconds)
2^2281-1 = 446087557183...2418132836351 (687 digits) is probable prime (37.575 seconds)
2^2293-1 = 182717463422...4672097697791 (691 digits) is not prime (16.324 seconds)
2^3217-1 = 259117086013...7362909315071 (969 digits) is probable prime (111.373 seconds)
2^3221-1 = 414587337621...7806549041151 (970 digits) is not prime (36.390 seconds)
</pre>
Above 1000 digits it becomes very slow.
=={{header|Ring}}==
| |||