Carmichael 3 strong pseudoprimes: Difference between revisions
Carmichael 3 strong pseudoprimes (view source)
Revision as of 09:19, 13 November 2023
, 6 months ago→{{header|RPL}}: tweaked the code
Drkameleon (talk | contribs) (added Arturo) |
m (→{{header|RPL}}: tweaked the code) |
||
| (7 intermediate revisions by 6 users not shown) | |||
Line 179:
IF is prime[ prime3 ] THEN
IF ( prime2 * prime3 ) MOD ( prime1 - 1 ) = 1 THEN
print( ( whole( prime1, 0 ), " ", whole( prime2, 0 ), " ", whole( prime3, 0 )
print( ( newline ) )
FI
FI
Line 218 ⟶ 219:
61 3361 4021
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">printOneLine: function [a,b,c,d]->
Line 468 ⟶ 470:
</pre>
=={{header|
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="
isprime[i] = 1
next i
Line 505 ⟶ 507:
for i = 2 to 61
call carmichael3(i)
next i
end</syntaxhighlight>
==={{header|Chipmunk Basic}}===
{{trans|FreeBASIC}}
{{works with|Chipmunk Basic|3.6.4}}
<syntaxhighlight lang="vbnet">100 cls
110 max_sieve = 10000000 ' 10^7
120 dim isprime(max_sieve)
130 sub carmichael3(p1)
140 if isprime(p1) = 0 then goto 440
150 for h3 = 1 to p1-1
160 t1 = (h3+p1)*(p1-1)
170 t2 = (-p1*p1) mod h3
180 if t2 < 0 then t2 = t2+h3
190 for d = 1 to h3+p1-1
200 if t1 mod d = 0 and t2 = (d mod h3) then
210 p2 = 1+int(t1/d)
220 if isprime(p2) = 0 then goto 270
230 p3 = 1+int(p1*p2/h3)
240 if isprime(p3) = 0 or ((p2*p3) mod (p1-1)) <> 1 then goto 270
250 print format$(p1,"###");" * ";format$(p2,"####");" * ";format$(p3,"#####")
260 endif
270 next d
280 next h3
290 end sub
300 'set up sieve
310 for i = 3 to max_sieve step 2
320 isprime(i) = 1
330 next i
340 isprime(2) = 1
350 for i = 3 to sqr(max_sieve) step 2
360 if isprime(i) = 1 then
370 for j = i*i to max_sieve step i*2
380 isprime(j) = 0
390 next j
400 endif
410 next i
420 for i = 2 to 61
430 carmichael3(i)
440 next i
450 end</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|Gambas}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">Public isprime[1000000] As Integer
Public Sub Main()
Dim max_sieve As Integer = 1000000
Dim i As Integer, j As Integer
'set up sieve
For i = 3 To max_sieve Step 2
isprime[i] = 1
Next
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
End If
Next
For i = 2 To 61
If isprime[i] <> 0 Then carmichael3(i)
Next
End
Sub carmichael3(p1 As Integer)
Dim h3 As Integer, d As Integer
Dim p2 As Integer, p3 As Integer, t1 As Integer, t2 As Integer
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
p3 = 1 + ((p1 * p2) \ h3)
If isprime[p3] = 0 Or ((p2 * p3) Mod (p1 - 1)) <> 1 Then Continue
Print Format$(p1, "###"); " * "; Format$(p2, "####"); " * "; Format$(p3, "#####")
End If
Next
Next
End Sub</syntaxhighlight>
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">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}}==
<syntaxhighlight lang="c">
Line 913 ⟶ 1,210:
61 x 241 x 421
61 x 3361 x 4021</pre>
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight>
func isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
proc carmichael3 p1 . .
for h3 = 1 to p1 - 1
for d = 1 to h3 + p1 - 1
if (h3 + p1) * (p1 - 1) mod d = 0 and -p1 * p1 mod h3 = d mod h3
p2 = 1 + (p1 - 1) * (h3 + p1) div d
if isprim p2 = 1
p3 = 1 + (p1 * p2 div h3)
if isprim p3 = 1 and (p2 * p3) mod (p1 - 1) = 1
print p1 & " " & p2 & " " & p3
.
.
.
.
.
.
for p1 = 2 to 61
if isprim p1 = 1
carmichael3 p1
.
.
</syntaxhighlight>
=={{header|EchoLisp}}==
<syntaxhighlight lang="scheme">
Line 955 ⟶ 1,287:
💥 824389441 = 61 x 3361 x 4021
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]
Line 1,255 ⟶ 1,588:
61 3361 4021 824389441
</pre>
=={{header|Go}}==
<syntaxhighlight lang="go">package main
Line 3,082 ⟶ 3,286:
61 3361 4021 824389441
</pre>
=={{header|RPL}}==
{{works with|HP|49}}
« { }
3 ROT '''FOR''' p1
2 p1 1 - '''FOR''' h3
1 h3 p1 + 1 - '''FOR''' d
'''IF''' h3 p1 + p1 1 - * d MOD NOT p1 SQ NEG h3 MOD d h3 MOD == AND '''THEN'''
p1 1 - h3 p1 + d IQUOT * 1 +
'''CASE'''
DUP ISPRIME? NOT '''THEN''' DROP '''END'''
p1 OVER * h3 IQUOT 1 +
DUP ISPRIME? NOT '''THEN''' DROP2 '''END'''
DUP2 * p1 1 - MOD 1 ≠ '''THEN''' DROP2 '''END'''
p1 UNROT 3 →LIST 1 →LIST +
'''END'''
'''END'''
'''NEXT'''
'''NEXT'''
p1 NEXTPRIME 1 - 'p1' STO
'''NEXT'''
» '<span style="color:blue">CARMIC</span>' STO
61 <span style="color:blue">CARMIC</span>
{{out}}
<pre>
1: { { 3 11 17 } { 5 29 73 } { 5 17 29 } { 5 13 17 } { 7 19 67 } { 7 31 73 } { 7 13 31 } { 7 73 103 } { 7 13 19 } { 13 61 397 } { 13 37 241 } { 13 97 421 } { 13 37 97 } { 13 37 61 } { 17 353 1201 } { 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 241 761 } { 41 241 521 } { 43 631 13567 } { 43 127 2731 } { 43 127 1093 } { 43 211 757 } { 43 631 1597 } { 43 127 211 } { 43 211 337 } { 43 547 673 } { 43 3361 3907 } { 47 3359 6073 } { 47 1151 1933 } { 47 3727 5153 } { 53 53 937 } { 53 157 2081 } { 53 157 521 } { 59 1451 2089 } { 61 421 12841 } { 61 181 5521 } { 61 61 1861 } { 61 61 1861 } { 61 181 1381 } { 61 541 3001 } { 61 661 2521 } { 61 241 421 } { 61 3361 4021 } }
</pre>
=={{header|Ruby}}==
{{works with|Ruby|1.9}}
Line 3,191 ⟶ 3,423:
61 x 3361 x 4021
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">
Line 3,750 ⟶ 3,983:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="
import "./math" for Int
var mod = Fn.new { |n, m| ((n%m) + m) % m }
Line 3,857 ⟶ 4,090:
61 3361 4021 824389441
</pre>
=={{header|zkl}}==
Using the Miller-Rabin primality test in lib GMP.
Line 3,890 ⟶ 4,124:
61 * 3361 * 4021 = 824389441
</pre>
| |||