Carmichael 3 strong pseudoprimes: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 36:
=={{header|11l}}==
{{trans|D}}
<
R ((n % m) + m) % m
Line 67:
I !is_prime(r) | (q * r) % (p - 1) != 1
L.continue
print(p‘ x ’q‘ x ’r)</
{{out}}
<pre>
Line 93:
Uses the Miller_Rabin package from
[[Miller-Rabin primality test#ordinary integers]].
<
procedure Nemesis is
Line 133:
end if;
end loop;
end Nemesis;</
{{out}}
Line 150:
=={{header|ALGOL 68}}==
Uses the Sieve of Eratosthenes code from the Smith Numbers task with an increased upper-bound (included here for convenience).
<
PROC sieve = ( REF[]BOOL s )VOID:
BEGIN
Line 190:
OD
FI
OD</
{{out}}
<pre>
Line 223:
=={{header|AWK}}==
<
# syntax: GAWK -f CARMICHAEL_3_STRONG_PSEUDOPRIMES.AWK
# converted from C
Line 266:
return(((n%m)+m)%m)
}
</syntaxhighlight>
{{out}}
<pre>
Line 345:
=={{header|BASIC256}}==
{{trans|FreeBASIC}}
<
for i = 3 to max_sieve step 2
isprime[i] = 1
Line 382:
next i
end
</syntaxhighlight>
=={{header|C}}==
<syntaxhighlight lang=C>
#include <stdio.h>
Line 435:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 456:
=={{header|C++}}==
<
#include <iostream>
Line 509:
}
return 0;
}</
{{out}}
Line 585:
=={{header|Clojure}}==
<
(ns example
(:gen-class))
Line 613:
(doseq [t numbers]
(println (format "%5d x %5d x %5d = %10d" (first t) (second t) (last t) (apply * t))))
</syntaxhighlight>
{{Out}}
<pre>
Line 690:
=={{header|D}}==
<
bool isPrime(in uint n) pure nothrow @nogc {
Line 722:
}
}
}</
{{out}}
<pre>3 x 11 x 17
Line 795:
=={{header|EchoLisp}}==
<
;; charmichaël numbers up to N-th prime ; 61 is 18-th prime
(define (charms (N 18) local: (h31 0) (Prime2 0) (Prime3 0))
Line 810:
#:when (= 1 (modulo (* Prime2 Prime3) (1- Prime1)))
(printf " 💥 %12d = %d x %d x %d" (* Prime1 Prime2 Prime3) Prime1 Prime2 Prime3)))
</syntaxhighlight>
{{out}}
<
(charms 3)
💥 561 = 3 x 11 x 17
Line 835:
💥 6189121 = 61 x 241 x 421
💥 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#)]
<
// Carmichael Number . Nigel Galloway: November 19th., 2017
let fN n = Seq.collect ((fun g->(Seq.map(fun e->(n,1+(n-1)*(n+g)/e,g,e))){1..(n+g-1)})){2..(n-1)}
Line 848:
let carms g = primes|>Seq.takeWhile(fun n->n<=g)|>Seq.collect fN|>Seq.choose fG
carms 61 |> Seq.iter (fun (P1,P2,P3)->printfn "%2d x %4d x %5d = %10d" P1 P2 P3 ((uint64 P3)*(uint64 (P1*P2))))
</syntaxhighlight>
{{out}}
<pre>
Line 924:
=={{header|Factor}}==
Note the use of <code>rem</code> instead of <code>mod</code> when the remainder should always be positive.
<
sequences ;
IN: rosetta-code.carmichael
Line 946:
: carmichael-demo ( -- ) 61 primes-upto [ carmichael ] each ;
MAIN: carmichael-demo</
{{out}}
<pre>
Line 1,024:
This is F77 style, and directly translates the given calculation as per ''formula translation''. It turns out that the normal integers suffice for the demonstration, except for just one of the products of the three primes: 41x1721x35281 = 2489462641, which is bigger than 2147483647, the 32-bit limit. Fortunately, INTEGER*8 variables are also available, so the extension is easy. Otherwise, one would have to mess about with using two integers in a bignum style, one holding say the millions, and the second the number up to a million.
===Source===
So, using the double MOD approach (see the ''Discussion'') - which gives the same result for either style of MOD... <
INTEGER N !Despite this intimidating allowance of 32 bits...
INTEGER F !A possible factor.
Line 1,063:
END IF
END DO
END</
===Output===
Line 1,141:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 1,199:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre> 3 * 11 * 17
Line 1,272:
=={{header|Go}}==
<
import "fmt"
Line 1,319:
if isPrime(p1) { carmichael(p1) }
}
}</
{{out}}
Line 1,403:
{{Works with|GHC|7.4.1}}
{{Works with|primes|0.2.1.0}}
<
import Data.Numbers.Primes
Line 1,420:
return (p, q, r)
main = putStr $ unlines $ map show carmichaels</
{{out}}
<pre>
Line 1,497:
The following works in both languages.
<
procedure main(A)
Line 1,520:
procedure format(p1,p2,p3)
return left(p1||" * "||p2||" * "||p3,20)||" = "||(p1*p2*p3)
end</
Output, with middle lines elided:
Line 1,556:
=={{header|J}}==
<syntaxhighlight lang=J>
q =: (,"0 1~ >:@i.@<:@+/"1)&.>@(,&.>"0 1~ >:@i.)&.>@I.@(1&p:@i.)@>:
f1 =: (0: = {. | <:@{: * 1&{ + {:) *. ((1&{ | -@*:@{:) = 1&{ | {.)
Line 1,563:
p3 =: 3:$0:`((* 1&p:)@({: , {. , (<.@>:@(1&{ %~ {. * {:))))@.(*@{.)@(p2 , }.)
(-. 3:$0:)@(((*"0 f2)@p3"1)@;@;@q) 61
</syntaxhighlight>
Output
<pre>
Line 1,639:
=={{header|Java}}==
{{trans|D}}
<
static int mod(int n, int m) {
Line 1,677:
}
}
}</
<pre>3 x 11 x 17
5 x 29 x 73
Line 1,752:
'''Function'''
<
function carmichael(pmax::Integer)
Line 1,772:
end
return reshape(car, 3, length(car) ÷ 3)
end</
'''Main'''
<
car = carmichael(hi)
Line 1,796:
@printf("p× %d × %d = %d ", q, r, c)
end
println("\n\n", size(car)[2], " results in total.")</
{{out}}
Line 1,846:
=={{header|Kotlin}}==
{{trans|D}}
<
return when {
this == 2 -> true
Line 1,881:
}
}
}</
{{out}}
See D output.
=={{header|Lua}}==
<
if n < 2 then return false end
if n % 2 == 0 then return n==2 end
Line 1,926:
end
end
print(found.." found.")</
{{out}}
<pre style="height:30ex;overflow:scroll">3 × 11 × 17 = 561
Line 2,000:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
Cases[Table[{p1, h3, d}, {p1, Array[Prime, PrimePi@61]}, {h3, 2,
p1 - 1}, {d, 1, h3 + p1 - 1}], {p1_Integer, h3_, d_} /;
Line 2,007:
Infinity], {p1_, p2_, h3_} /; PrimeQ[1 + Floor[p1 p2/h3]] :> {p1,
p2, 1 + Floor[p1 p2/h3]}], {p1_, p2_, p3_} /;
Mod[p2 p3, p1 - 1] == 1 :> Print[p1, "*", p2, "*", p3]]</
=={{header|Nim}}==
{{trans|Vala}} with some modifications
<
func isPrime(n: int64): bool =
Line 2,041:
if not isPrime(r) or (q * r) mod (p - 1) != 1:
continue
echo &"{p:5} × {q:5} × {r:5} = {p * q * r:10}"</
{{out}}
<pre>
Line 2,116:
=={{header|PARI/GP}}==
<
my(v=List(),q,r);
for(h=2,p-1,
Line 2,127:
Set(v)
};
forprime(p=3,67,v=f(p); for(i=1,#v,print1(v[i]", ")))</
{{out}}
<pre>561, 1105, 2465, 10585, 1729, 2821, 6601, 8911, 15841, 52633, 29341, 46657, 115921, 314821, 530881, 162401, 7207201, 334153, 1024651, 1615681, 3581761, 5444489, 399001, 512461, 1193221, 1857241, 5049001, 5481451, 471905281, 294409, 488881, 1461241, 8134561, 36765901, 252601, 410041, 1909001, 5148001, 7519441, 434932961, 2489462641, 1152271, 3057601, 5968873, 6868261, 11972017, 14913991, 15829633, 43331401, 67902031, 368113411, 564651361, 104569501, 902645857, 958762729, 2508013, 4335241, 17316001, 178837201, 6189121, 9439201, 15247621, 35703361, 60957361, 99036001, 101649241, 329769721, 824389441, 1574601601, 10267951, 163954561, 7991602081,</pre>
Line 2,133:
=={{header|Perl}}==
{{libheader|ntheory}}
<
forprimes { my $p = $_;
Line 2,149:
}
}
} 3,61;</
{{out}}
<pre>
Line 2,164:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
Line 2,190:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d Carmichael numbers found\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 2,206:
=={{header|PicoLisp}}==
<
(% (+ Y (% X Y)) Y) )
Line 2,245:
(prinl)
(bye)</
=={{header|PL/I}}==
<
declare (Prime1, Prime2, Prime3, h3, d) fixed binary (31);
Line 2,274:
/* Uses is_prime from Rosetta Code PL/I. */
end Carmichael;</
Results:
<pre>
Line 2,373:
=={{header|Prolog}}==
<
show(Limit) :-
forall(
Line 2,405:
N mod D =\= 0,
D2 is D + A, prime(N, D2, As).
</syntaxhighlight>
{{Out}}
<pre>
Line 2,524:
=={{header|Python}}==
<
'''
Extensible sieve of Eratosthenes
Line 2,594:
ans = sorted(sum((carmichael(n) for n in range(62) if isprime(n)), []))
print(',\n'.join(repr(ans[i:i+5])[1:-1] for i in range(0, len(ans)+1, 5)))</
{{out}}
<pre>(3, 11, 17), (5, 13, 17), (5, 17, 29), (5, 29, 73), (7, 13, 19),
Line 2,612:
=={{header|Racket}}==
<
#lang racket
(require math)
Line 2,629:
(displayln (list p1 p2 p3 '=> (* p1 p2 p3))))))
(next (+ d 1))))))
</syntaxhighlight>
Output:
<
(3 11 17 => 561)
(5 29 73 => 10585)
Line 2,694:
(61 241 421 => 6189121)
(61 3361 4021 => 824389441)
</syntaxhighlight>
=={{header|Raku}}==
Line 2,700:
{{works with|Rakudo|2015.12}}
An almost direct translation of the pseudocode. We take the liberty of going up to 67 to show we aren't limited to 32-bit integers. (Raku uses arbitrary precision in any case.)
<syntaxhighlight lang=raku
for 1 ^..^ Prime1 -> \h3 {
my \g = h3 + Prime1;
Line 2,714:
}
}
}</
{{out}}
<pre>3 × 11 × 17 == 561
Line 2,795:
Some code optimization was done, while not necessary for the small default number ('''61'''), it was significant for larger numbers.
<
numeric digits 18 /*handle big dig #s (9 is the default).*/
parse arg N .; if N=='' | N=="," then N=61 /*allow user to specify for the search.*/
Line 2,836:
if x//(k+2) ==0 then return 0
end /*k*/
@.x=1; return 1</
'''output''' when using the default input:
<pre>
Line 2,868:
=={{header|Ring}}==
<
# Project : Carmichael 3 strong pseudoprimes
Line 2,912:
next
return 1
</syntaxhighlight>
Output:
<pre>
Line 2,991:
=={{header|Ruby}}==
{{works with|Ruby|1.9}}
<
require 'prime'
Line 3,008:
end
puts
end</
{{out}}
Line 3,100:
=={{header|Rust}}==
<
fn is_prime(n: i64) -> bool {
if n > 1 {
Line 3,152:
.count(); // Evaluate entire iterator
}
</syntaxhighlight>
{{out}}
<pre>
Line 3,171:
The function [http://seed7.sourceforge.net/algorith/math.htm#isPrime isPrime] below is borrowed from the [http://seed7.sourceforge.net/algorith Seed7 algorithm collection].
<
const func boolean: isPrime (in integer: number) is func
Line 3,218:
end if;
end for;
end func;</
{{out}}
Line 3,295:
=={{header|Sidef}}==
{{trans|Perl}}
<
for (a = (a-1 -> next_prime); a <= b; a.next_prime!) {
callback(a)
Line 3,315:
}
}
})</
{{out}}
Line 3,334:
{{trans|Rust}}
<
extension BinaryInteger {
Line 3,403:
for c in res {
print(c)
}</
{{out}}
Line 3,420:
=={{header|Tcl}}==
Using the primality tester from [[Miller-Rabin primality test#Tcl|the Miller-Rabin task]]...
<
set carmichaels {}
for {set p1 2} {$p1 <= $limit} {incr p1} {
Line 3,442:
}
return $carmichaels
}</
Demonstrating:
<
puts "[expr {[llength $results]/4}] Carmichael numbers found"
foreach {p1 p2 p3 c} $results {
puts "$p1 x $p2 x $p3 = $c"
}</
{{out}}
<pre>
Line 3,525:
=={{header|Vala}}==
{{trans|D}}
<
return ((n % m) + m) % m;
}
Line 3,557:
}
}
}</
{{out}}
<pre>
Line 3,664:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<
import "/math" for Int
Line 3,693:
for (p1 in 2..61) {
if (Int.isPrime(p1)) carmichael.call(p1)
}</
{{out}}
Line 3,774:
=={{header|zkl}}==
Using the Miller-Rabin primality test in lib GMP.
<
primes:=T(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61);
var p2,p3;
Line 3,785:
{ T(p1,p2,p3) } // return list of three primes in Carmichael number
]];
fcn mod(a,b) { m:=a%b; if(m<0) m+b else m }</
<
cs.pump(Console.println,fcn([(p1,p2,p3)]){
"%2d * %4d * %5d = %d".fmt(p1,p2,p3,p1*p2*p3) });</
{{out}}
<pre>
Line 3,808:
=={{header|ZX Spectrum Basic}}==
{{trans|C}}
<
20 LET n=p: GO SUB 1000
30 IF NOT n THEN GO TO 200
Line 3,834:
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>
|