Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
(Carmichael 3 strong pseudoprimes in Yabasic) |
(Dialects of BASIC moved to the BASIC section.) |
||
Line 468: | Line 468: | ||
</pre> |
</pre> |
||
=={{header| |
=={{header|BASIC}}== |
||
==={{header|BASIC256}}=== |
|||
{{trans|FreeBASIC}} |
{{trans|FreeBASIC}} |
||
<syntaxhighlight lang="basic256"> |
<syntaxhighlight lang="basic256"> |
||
Line 508: | Line 509: | ||
end |
end |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
==={{header|FreeBASIC}}=== |
|||
<syntaxhighlight lang="freebasic">' version 17-10-2016 |
|||
' compile with: fbc -s console |
|||
' using a sieve for finding primes |
|||
#Define max_sieve 10000000 ' 10^7 |
|||
ReDim Shared As Byte isprime(max_sieve) |
|||
' translated the pseudo code to FreeBASIC |
|||
Sub carmichael3(p1 As Integer) |
|||
If isprime(p1) = 0 Then Exit Sub |
|||
Dim As Integer h3, d, p2, p3, t1, t2 |
|||
For h3 = 1 To p1 -1 |
|||
t1 = (h3 + p1) * (p1 -1) |
|||
t2 = (-p1 * p1) Mod h3 |
|||
If t2 < 0 Then t2 = t2 + h3 |
|||
For d = 1 To h3 + p1 -1 |
|||
If t1 Mod d = 0 And t2 = (d Mod h3) Then |
|||
p2 = 1 + (t1 \ d) |
|||
If isprime(p2) = 0 Then Continue For |
|||
p3 = 1 + (p1 * p2 \ h3) |
|||
If isprime(p3) = 0 Or ((p2 * p3) Mod (p1 -1)) <> 1 Then Continue For |
|||
Print Using "### * #### * #####"; p1; p2; p3 |
|||
End If |
|||
Next d |
|||
Next h3 |
|||
End Sub |
|||
' ------=< MAIN >=------ |
|||
Dim As UInteger i, j |
|||
'set up sieve |
|||
For i = 3 To max_sieve Step 2 |
|||
isprime(i) = 1 |
|||
Next i |
|||
isprime(2) = 1 |
|||
For i = 3 To Sqr(max_sieve) Step 2 |
|||
If isprime(i) = 1 Then |
|||
For j = i * i To max_sieve Step i * 2 |
|||
isprime(j) = 0 |
|||
Next j |
|||
End If |
|||
Next i |
|||
For i = 2 To 61 |
|||
carmichael3(i) |
|||
Next i |
|||
' empty keyboard buffer |
|||
While InKey <> "" : Wend |
|||
Print : Print "hit any key to end program" |
|||
Sleep |
|||
End</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 3 * 11 * 17 |
|||
5 * 29 * 73 |
|||
5 * 17 * 29 |
|||
5 * 13 * 17 |
|||
7 * 19 * 67 |
|||
7 * 31 * 73 |
|||
7 * 13 * 31 |
|||
7 * 23 * 41 |
|||
7 * 73 * 103 |
|||
7 * 13 * 19 |
|||
13 * 61 * 397 |
|||
13 * 37 * 241 |
|||
13 * 97 * 421 |
|||
13 * 37 * 97 |
|||
13 * 37 * 61 |
|||
17 * 41 * 233 |
|||
17 * 353 * 1201 |
|||
19 * 43 * 409 |
|||
19 * 199 * 271 |
|||
23 * 199 * 353 |
|||
29 * 113 * 1093 |
|||
29 * 197 * 953 |
|||
31 * 991 * 15361 |
|||
31 * 61 * 631 |
|||
31 * 151 * 1171 |
|||
31 * 61 * 271 |
|||
31 * 61 * 211 |
|||
31 * 271 * 601 |
|||
31 * 181 * 331 |
|||
37 * 109 * 2017 |
|||
37 * 73 * 541 |
|||
37 * 613 * 1621 |
|||
37 * 73 * 181 |
|||
37 * 73 * 109 |
|||
41 * 1721 * 35281 |
|||
41 * 881 * 12041 |
|||
41 * 101 * 461 |
|||
41 * 241 * 761 |
|||
41 * 241 * 521 |
|||
41 * 73 * 137 |
|||
41 * 61 * 101 |
|||
43 * 631 * 13567 |
|||
43 * 271 * 5827 |
|||
43 * 127 * 2731 |
|||
43 * 127 * 1093 |
|||
43 * 211 * 757 |
|||
43 * 631 * 1597 |
|||
43 * 127 * 211 |
|||
43 * 211 * 337 |
|||
43 * 433 * 643 |
|||
43 * 547 * 673 |
|||
43 * 3361 * 3907 |
|||
47 * 3359 * 6073 |
|||
47 * 1151 * 1933 |
|||
47 * 3727 * 5153 |
|||
53 * 157 * 2081 |
|||
53 * 79 * 599 |
|||
53 * 157 * 521 |
|||
59 * 1451 * 2089 |
|||
61 * 421 * 12841 |
|||
61 * 181 * 5521 |
|||
61 * 1301 * 19841 |
|||
61 * 277 * 2113 |
|||
61 * 181 * 1381 |
|||
61 * 541 * 3001 |
|||
61 * 661 * 2521 |
|||
61 * 271 * 571 |
|||
61 * 241 * 421 |
|||
61 * 3361 * 4021</pre> |
|||
==={{header|Yabasic}}=== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="vb">max_sieve = 1e7 |
|||
dim isprime(max_sieve) |
|||
//set up sieve |
|||
for i = 3 to max_sieve step 2 |
|||
isprime(i) = 1 |
|||
next i |
|||
isprime(2) = 1 |
|||
for i = 3 to sqrt(max_sieve) step 2 |
|||
if isprime(i) = 1 then |
|||
for j = i * i to max_sieve step i * 2 |
|||
isprime(j) = 0 |
|||
next j |
|||
fi |
|||
next i |
|||
for i = 2 to 61 |
|||
carmichael3(i) |
|||
next i |
|||
end |
|||
sub carmichael3(p1) |
|||
local h3, d, p2, p3, t1, t2 |
|||
if isprime(p1) = 0 return |
|||
for h3 = 1 to p1 -1 |
|||
t1 = (h3 + p1) * (p1 -1) |
|||
t2 = mod((-p1 * p1), h3) |
|||
if t2 < 0 t2 = t2 + h3 |
|||
for d = 1 to h3 + p1 -1 |
|||
if mod(t1, d) = 0 and t2 = mod(d, h3) then |
|||
p2 = 1 + int(t1 / d) |
|||
if isprime(p2) = 0 continue |
|||
p3 = 1 + int(p1 * p2 / h3) |
|||
if isprime(p3) = 0 or mod((p2 * p3), (p1 -1)) <> 1 continue |
|||
print p1 using ("###"), " * ", p2 using ("####"), " * ", p3 using ("#####") |
|||
fi |
|||
next d |
|||
next h3 |
|||
end sub</syntaxhighlight> |
|||
==={{header|ZX Spectrum Basic}}=== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="zxbasic">10 FOR p=2 TO 61 |
|||
20 LET n=p: GO SUB 1000 |
|||
30 IF NOT n THEN GO TO 200 |
|||
40 FOR h=1 TO p-1 |
|||
50 FOR d=1 TO h-1+p |
|||
60 IF NOT (FN m((h+p)*(p-1),d)=0 AND FN w(-p*p,h)=FN m(d,h)) THEN GO TO 180 |
|||
70 LET q=INT (1+((p-1)*(h+p)/d)) |
|||
80 LET n=q: GO SUB 1000 |
|||
90 IF NOT n THEN GO TO 180 |
|||
100 LET r=INT (1+(p*q/h)) |
|||
110 LET n=r: GO SUB 1000 |
|||
120 IF (NOT n) OR ((FN m((q*r),(p-1))<>1)) THEN GO TO 180 |
|||
130 PRINT p;" ";q;" ";r |
|||
180 NEXT d |
|||
190 NEXT h |
|||
200 NEXT p |
|||
210 STOP |
|||
1000 IF n<4 THEN LET n=(n>1): RETURN |
|||
1010 IF (NOT FN m(n,2)) OR (NOT FN m(n,3)) THEN LET n=0: RETURN |
|||
1020 LET i=5 |
|||
1030 IF NOT ((i*i)<=n) THEN LET n=1: RETURN |
|||
1040 IF (NOT FN m(n,i)) OR NOT FN m(n,(i+2)) THEN LET n=0: RETURN |
|||
1050 LET i=i+6 |
|||
1060 GO TO 1030 |
|||
2000 DEF FN m(a,b)=a-(INT (a/b)*b): REM Mod function |
|||
2010 DEF FN w(a,b)=FN m(FN m(a,b)+b,b): REM Mod function modified |
|||
</syntaxhighlight> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
<syntaxhighlight lang="c"> |
<syntaxhighlight lang="c"> |
||
Line 1,255: | Line 1,461: | ||
61 3361 4021 824389441 |
61 3361 4021 824389441 |
||
</pre> |
</pre> |
||
=={{header|FreeBASIC}}== |
|||
<syntaxhighlight lang="freebasic">' version 17-10-2016 |
|||
' compile with: fbc -s console |
|||
' using a sieve for finding primes |
|||
#Define max_sieve 10000000 ' 10^7 |
|||
ReDim Shared As Byte isprime(max_sieve) |
|||
' translated the pseudo code to FreeBASIC |
|||
Sub carmichael3(p1 As Integer) |
|||
If isprime(p1) = 0 Then Exit Sub |
|||
Dim As Integer h3, d, p2, p3, t1, t2 |
|||
For h3 = 1 To p1 -1 |
|||
t1 = (h3 + p1) * (p1 -1) |
|||
t2 = (-p1 * p1) Mod h3 |
|||
If t2 < 0 Then t2 = t2 + h3 |
|||
For d = 1 To h3 + p1 -1 |
|||
If t1 Mod d = 0 And t2 = (d Mod h3) Then |
|||
p2 = 1 + (t1 \ d) |
|||
If isprime(p2) = 0 Then Continue For |
|||
p3 = 1 + (p1 * p2 \ h3) |
|||
If isprime(p3) = 0 Or ((p2 * p3) Mod (p1 -1)) <> 1 Then Continue For |
|||
Print Using "### * #### * #####"; p1; p2; p3 |
|||
End If |
|||
Next d |
|||
Next h3 |
|||
End Sub |
|||
' ------=< MAIN >=------ |
|||
Dim As UInteger i, j |
|||
'set up sieve |
|||
For i = 3 To max_sieve Step 2 |
|||
isprime(i) = 1 |
|||
Next i |
|||
isprime(2) = 1 |
|||
For i = 3 To Sqr(max_sieve) Step 2 |
|||
If isprime(i) = 1 Then |
|||
For j = i * i To max_sieve Step i * 2 |
|||
isprime(j) = 0 |
|||
Next j |
|||
End If |
|||
Next i |
|||
For i = 2 To 61 |
|||
carmichael3(i) |
|||
Next i |
|||
' empty keyboard buffer |
|||
While InKey <> "" : Wend |
|||
Print : Print "hit any key to end program" |
|||
Sleep |
|||
End</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 3 * 11 * 17 |
|||
5 * 29 * 73 |
|||
5 * 17 * 29 |
|||
5 * 13 * 17 |
|||
7 * 19 * 67 |
|||
7 * 31 * 73 |
|||
7 * 13 * 31 |
|||
7 * 23 * 41 |
|||
7 * 73 * 103 |
|||
7 * 13 * 19 |
|||
13 * 61 * 397 |
|||
13 * 37 * 241 |
|||
13 * 97 * 421 |
|||
13 * 37 * 97 |
|||
13 * 37 * 61 |
|||
17 * 41 * 233 |
|||
17 * 353 * 1201 |
|||
19 * 43 * 409 |
|||
19 * 199 * 271 |
|||
23 * 199 * 353 |
|||
29 * 113 * 1093 |
|||
29 * 197 * 953 |
|||
31 * 991 * 15361 |
|||
31 * 61 * 631 |
|||
31 * 151 * 1171 |
|||
31 * 61 * 271 |
|||
31 * 61 * 211 |
|||
31 * 271 * 601 |
|||
31 * 181 * 331 |
|||
37 * 109 * 2017 |
|||
37 * 73 * 541 |
|||
37 * 613 * 1621 |
|||
37 * 73 * 181 |
|||
37 * 73 * 109 |
|||
41 * 1721 * 35281 |
|||
41 * 881 * 12041 |
|||
41 * 101 * 461 |
|||
41 * 241 * 761 |
|||
41 * 241 * 521 |
|||
41 * 73 * 137 |
|||
41 * 61 * 101 |
|||
43 * 631 * 13567 |
|||
43 * 271 * 5827 |
|||
43 * 127 * 2731 |
|||
43 * 127 * 1093 |
|||
43 * 211 * 757 |
|||
43 * 631 * 1597 |
|||
43 * 127 * 211 |
|||
43 * 211 * 337 |
|||
43 * 433 * 643 |
|||
43 * 547 * 673 |
|||
43 * 3361 * 3907 |
|||
47 * 3359 * 6073 |
|||
47 * 1151 * 1933 |
|||
47 * 3727 * 5153 |
|||
53 * 157 * 2081 |
|||
53 * 79 * 599 |
|||
53 * 157 * 521 |
|||
59 * 1451 * 2089 |
|||
61 * 421 * 12841 |
|||
61 * 181 * 5521 |
|||
61 * 1301 * 19841 |
|||
61 * 277 * 2113 |
|||
61 * 181 * 1381 |
|||
61 * 541 * 3001 |
|||
61 * 661 * 2521 |
|||
61 * 271 * 571 |
|||
61 * 241 * 421 |
|||
61 * 3361 * 4021</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
<syntaxhighlight lang="go">package main |
<syntaxhighlight lang="go">package main |
||
Line 3,857: | Line 3,934: | ||
61 3361 4021 824389441 |
61 3361 4021 824389441 |
||
</pre> |
</pre> |
||
=={{header|Yabasic}}== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="vb">max_sieve = 1e7 |
|||
dim isprime(max_sieve) |
|||
//set up sieve |
|||
for i = 3 to max_sieve step 2 |
|||
isprime(i) = 1 |
|||
next i |
|||
isprime(2) = 1 |
|||
for i = 3 to sqrt(max_sieve) step 2 |
|||
if isprime(i) = 1 then |
|||
for j = i * i to max_sieve step i * 2 |
|||
isprime(j) = 0 |
|||
next j |
|||
fi |
|||
next i |
|||
for i = 2 to 61 |
|||
carmichael3(i) |
|||
next i |
|||
end |
|||
sub carmichael3(p1) |
|||
local h3, d, p2, p3, t1, t2 |
|||
if isprime(p1) = 0 return |
|||
for h3 = 1 to p1 -1 |
|||
t1 = (h3 + p1) * (p1 -1) |
|||
t2 = mod((-p1 * p1), h3) |
|||
if t2 < 0 t2 = t2 + h3 |
|||
for d = 1 to h3 + p1 -1 |
|||
if mod(t1, d) = 0 and t2 = mod(d, h3) then |
|||
p2 = 1 + int(t1 / d) |
|||
if isprime(p2) = 0 continue |
|||
p3 = 1 + int(p1 * p2 / h3) |
|||
if isprime(p3) = 0 or mod((p2 * p3), (p1 -1)) <> 1 continue |
|||
print p1 using ("###"), " * ", p2 using ("####"), " * ", p3 using ("#####") |
|||
fi |
|||
next d |
|||
next h3 |
|||
end sub</syntaxhighlight> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
Line 3,935: | Line 3,968: | ||
61 * 3361 * 4021 = 824389441 |
61 * 3361 * 4021 = 824389441 |
||
</pre> |
</pre> |
||
=={{header|ZX Spectrum Basic}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="zxbasic">10 FOR p=2 TO 61 |
|||
20 LET n=p: GO SUB 1000 |
|||
30 IF NOT n THEN GO TO 200 |
|||
40 FOR h=1 TO p-1 |
|||
50 FOR d=1 TO h-1+p |
|||
60 IF NOT (FN m((h+p)*(p-1),d)=0 AND FN w(-p*p,h)=FN m(d,h)) THEN GO TO 180 |
|||
70 LET q=INT (1+((p-1)*(h+p)/d)) |
|||
80 LET n=q: GO SUB 1000 |
|||
90 IF NOT n THEN GO TO 180 |
|||
100 LET r=INT (1+(p*q/h)) |
|||
110 LET n=r: GO SUB 1000 |
|||
120 IF (NOT n) OR ((FN m((q*r),(p-1))<>1)) THEN GO TO 180 |
|||
130 PRINT p;" ";q;" ";r |
|||
180 NEXT d |
|||
190 NEXT h |
|||
200 NEXT p |
|||
210 STOP |
|||
1000 IF n<4 THEN LET n=(n>1): RETURN |
|||
1010 IF (NOT FN m(n,2)) OR (NOT FN m(n,3)) THEN LET n=0: RETURN |
|||
1020 LET i=5 |
|||
1030 IF NOT ((i*i)<=n) THEN LET n=1: RETURN |
|||
1040 IF (NOT FN m(n,i)) OR NOT FN m(n,(i+2)) THEN LET n=0: RETURN |
|||
1050 LET i=i+6 |
|||
1060 GO TO 1030 |
|||
2000 DEF FN m(a,b)=a-(INT (a/b)*b): REM Mod function |
|||
2010 DEF FN w(a,b)=FN m(FN m(a,b)+b,b): REM Mod function modified |
|||
</syntaxhighlight> |