Fermat pseudoprimes: Difference between revisions
Added FreeBasic
(Created Nim solution.) |
(Added FreeBasic) |
||
Line 312:
Real: 00:00:00.632
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="vb">'#include "isprime.bas"
Function powMod (a As Uinteger, n As Uinteger, m As Uinteger) As Uinteger
' Return "a^n mod m".
Dim As Uinteger a1 = a Mod m
Dim As Uinteger n1 = n
Dim As Uinteger result
If a1 > 0 Then
result = 1
While n1 > 0
If (n1 And 1) <> 0 Then result = (result * a1) Mod m
n1 Shr= 1
a1 = (a1 * a1) Mod m
Wend
End If
Return result
End Function
Function isFermatPseudoprime(x As Uinteger, a As Uinteger) As Boolean
Return Iif(isPrime(x), False, powMod(a, x - 1, x) = 1)
End Function
Dim As Uinteger a, b, limite = 50000
Print "First 20 Fermat pseudoprimes:"
For a = 1 To 20
Dim As Uinteger total = 0
Dim As Uinteger x = 2
Dim As Uinteger primer20(1 To 20)
For b = 1 To limite
While x <= b
If isFermatPseudoprime(x, a) Then
total += 1
If total <= 20 Then primer20(total) = x
End If
x += 1
Wend
Next
Print Using "Base ## to ##### total: #####_, first: "; a; limite; total;
For b = 1 To 20
Print Using "######"; primer20(b);
Next b
Print
Next a
Sleep</syntaxhighlight>
{{out}}
<pre>First 20 Fermat pseudoprimes:
Base 1 to 50000 total: 44866, first: 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32
Base 2 to 50000 total: 55, first: 341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 8321
Base 3 to 50000 total: 53, first: 91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 3281 3367 3751 4961 5551 6601
Base 4 to 50000 total: 111, first: 15 85 91 341 435 451 561 645 703 1105 1247 1271 1387 1581 1695 1729 1891 1905 2047 2071
Base 5 to 50000 total: 54, first: 4 124 217 561 781 1541 1729 1891 2821 4123 5461 5611 5662 5731 6601 7449 7813 8029 8911 9881
Base 6 to 50000 total: 74, first: 35 185 217 301 481 1105 1111 1261 1333 1729 2465 2701 2821 3421 3565 3589 3913 4123 4495 5713
Base 7 to 50000 total: 49, first: 6 25 325 561 703 817 1105 1825 2101 2353 2465 3277 4525 4825 6697 8321 10225 10585 10621 11041
Base 8 to 50000 total: 150, first: 9 21 45 63 65 105 117 133 153 231 273 341 481 511 561 585 645 651 861 949
Base 9 to 50000 total: 113, first: 4 8 28 52 91 121 205 286 364 511 532 616 671 697 703 946 949 1036 1105 1288
Base 10 to 50000 total: 65, first: 9 33 91 99 259 451 481 561 657 703 909 1233 1729 2409 2821 2981 3333 3367 4141 4187
Base 11 to 50000 total: 61, first: 10 15 70 133 190 259 305 481 645 703 793 1105 1330 1729 2047 2257 2465 2821 4577 4921
Base 12 to 50000 total: 91, first: 65 91 133 143 145 247 377 385 703 1045 1099 1105 1649 1729 1885 1891 2041 2233 2465 2701
Base 13 to 50000 total: 68, first: 4 6 12 21 85 105 231 244 276 357 427 561 1099 1785 1891 2465 2806 3605 5028 5149
Base 14 to 50000 total: 69, first: 15 39 65 195 481 561 781 793 841 985 1105 1111 1541 1891 2257 2465 2561 2665 2743 3277
Base 15 to 50000 total: 42, first: 14 341 742 946 1477 1541 1687 1729 1891 1921 2821 3133 3277 4187 6541 6601 7471 8701 8911 9073
Base 16 to 50000 total: 145, first: 15 51 85 91 255 341 435 451 561 595 645 703 1105 1247 1261 1271 1285 1387 1581 1687
Base 17 to 50000 total: 63, first: 4 8 9 16 45 91 145 261 781 1111 1228 1305 1729 1885 2149 2821 3991 4005 4033 4187
Base 18 to 50000 total: 98, first: 25 49 65 85 133 221 323 325 343 425 451 637 931 1105 1225 1369 1387 1649 1729 1921
Base 19 to 50000 total: 93, first: 6 9 15 18 45 49 153 169 343 561 637 889 905 906 1035 1105 1629 1661 1849 1891
Base 20 to 50000 total: 66, first: 21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059</pre>
=={{header|Julia}}==
| |||