Carmichael 3 strong pseudoprimes: Difference between revisions

=={{header|11l}}==

{{trans|D}}

R ((n % m) + m) % m

I !is_prime(r) | (q * r) % (p - 1) != 1

L.continue

{{out}}

<pre>

Uses the Miller_Rabin package from

[[Miller-Rabin primality test#ordinary integers]].

procedure Nemesis is

end if;

end loop;

{{out}}

=={{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

OD

FI

{{out}}

<pre>

=={{header|AWK}}==

# syntax: GAWK -f CARMICHAEL_3_STRONG_PSEUDOPRIMES.AWK

# converted from C

return(((n%m)+m)%m)

}

{{out}}

<pre>

=={{header|BASIC256}}==

{{trans|FreeBASIC}}

for i = 3 to max_sieve step 2

isprime[i] = 1

next i

end

=={{header|C}}==

#include <stdio.h>

return 0;

}

{{out}}

<pre>

=={{header|C++}}==

#include <iostream>

}

return 0;

{{out}}

=={{header|Clojure}}==

(ns example

(:gen-class))

(doseq [t numbers]

(println (format "%5d x %5d x %5d = %10d" (first t) (second t) (last t) (apply * t))))

{{Out}}

<pre>

=={{header|D}}==

bool isPrime(in uint n) pure nothrow @nogc {

}

}

{{out}}

<pre>3 x 11 x 17

=={{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))

#:when (= 1 (modulo (* Prime2 Prime3) (1- Prime1)))

(printf " 💥 %12d = %d x %d x %d" (* Prime1 Prime2 Prime3) Prime1 Prime2 Prime3)))

{{out}}

(charms 3)

💥 561 = 3 x 11 x 17

💥 6189121 = 61 x 241 x 421

💥 824389441 = 61 x 3361 x 4021

=={{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)}

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))))

{{out}}

<pre>

=={{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

: carmichael-demo ( -- ) 61 primes-upto [ carmichael ] each ;

{{out}}

<pre>

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===

INTEGER N !Despite this intimidating allowance of 32 bits...

INTEGER F !A possible factor.

END IF

END DO

===Output===

=={{header|FreeBASIC}}==

' compile with: fbc -s console

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> 3 * 11 * 17

=={{header|Go}}==

import "fmt"

if isPrime(p1) { carmichael(p1) }

}

{{out}}

{{Works with|GHC|7.4.1}}

{{Works with|primes|0.2.1.0}}

import Data.Numbers.Primes

return (p, q, r)

{{out}}

<pre>

The following works in both languages.

procedure main(A)

procedure format(p1,p2,p3)

return left(p1||" * "||p2||" * "||p3,20)||" = "||(p1*p2*p3)

Output, with middle lines elided:

=={{header|J}}==

q =: (,"0 1~ >:@i.@<:@+/"1)&.>@(,&.>"0 1~ >:@i.)&.>@I.@(1&p:@i.)@>:

f1 =: (0: = {. | <:@{: * 1&{ + {:) *. ((1&{ | -@*:@{:) = 1&{ | {.)

p3 =: 3:$0:`((* 1&p:)@({: , {. , (<.@>:@(1&{ %~ {. * {:))))@.(*@{.)@(p2 , }.)

(-. 3:$0:)@(((*"0 f2)@p3"1)@;@;@q) 61

Output

<pre>

=={{header|Java}}==

{{trans|D}}

static int mod(int n, int m) {

}

}

<pre>3 x 11 x 17

5 x 29 x 73

'''Function'''

function carmichael(pmax::Integer)

end

return reshape(car, 3, length(car) ÷ 3)

'''Main'''

car = carmichael(hi)

@printf("p× %d × %d = %d ", q, r, c)

end

{{out}}

=={{header|Kotlin}}==

{{trans|D}}

return when {

this == 2 -> true

}

}

{{out}}

See D output.

=={{header|Lua}}==

if n < 2 then return false end

if n % 2 == 0 then return n==2 end

end

end

{{out}}

<pre style="height:30ex;overflow:scroll">3 × 11 × 17 = 561

=={{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_} /;

Infinity], {p1_, p2_, h3_} /; PrimeQ[1 + Floor[p1 p2/h3]] :> {p1,

p2, 1 + Floor[p1 p2/h3]}], {p1_, p2_, p3_} /;

=={{header|Nim}}==

{{trans|Vala}} with some modifications

func isPrime(n: int64): bool =

if not isPrime(r) or (q * r) mod (p - 1) != 1:

continue

{{out}}

<pre>

=={{header|PARI/GP}}==

my(v=List(),q,r);

for(h=2,p-1,

Set(v)

};

{{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>

=={{header|Perl}}==

{{libheader|ntheory}}

forprimes { my $p = $_;

}

}

{{out}}

<pre>

=={{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>

<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>

=={{header|PicoLisp}}==

(% (+ Y (% X Y)) Y) )

(prinl)

=={{header|PL/I}}==

declare (Prime1, Prime2, Prime3, h3, d) fixed binary (31);

/* Uses is_prime from Rosetta Code PL/I. */

Results:

<pre>

=={{header|Prolog}}==

show(Limit) :-

forall(

N mod D =\= 0,

D2 is D + A, prime(N, D2, As).

{{Out}}

<pre>

=={{header|Python}}==

'''

Extensible sieve of Eratosthenes

ans = sorted(sum((carmichael(n) for n in range(62) if isprime(n)), []))

{{out}}

<pre>(3, 11, 17), (5, 13, 17), (5, 17, 29), (5, 29, 73), (7, 13, 19),

=={{header|Racket}}==

#lang racket

(require math)

(displayln (list p1 p2 p3 '=> (* p1 p2 p3))))))

(next (+ d 1))))))

Output:

(3 11 17 => 561)

(5 29 73 => 10585)

(61 241 421 => 6189121)

(61 3361 4021 => 824389441)

=={{header|Raku}}==

{{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.)

for 1 ^..^ Prime1 -> \h3 {

my \g = h3 + Prime1;

}

}

{{out}}

<pre>3 × 11 × 17 == 561

Some code optimization was done, while not necessary for the small default number ('''61'''), &nbsp; 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.*/

if x//(k+2) ==0 then return 0

end /*k*/

'''output''' &nbsp; when using the default input:

<pre>

=={{header|Ring}}==

# Project : Carmichael 3 strong pseudoprimes

next

return 1

Output:

<pre>

=={{header|Ruby}}==

{{works with|Ruby|1.9}}

require 'prime'

end

puts

{{out}}

=={{header|Rust}}==

fn is_prime(n: i64) -> bool {

if n > 1 {

.count(); // Evaluate entire iterator

}

{{out}}

<pre>

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

end if;

end for;

{{out}}

=={{header|Sidef}}==

{{trans|Perl}}

for (a = (a-1 -> next_prime); a <= b; a.next_prime!) {

callback(a)

}

}

{{out}}

{{trans|Rust}}

extension BinaryInteger {

for c in res {

print(c)

{{out}}

=={{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} {

}

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>

=={{header|Vala}}==

{{trans|D}}

return ((n % m) + m) % m;

}

}

}

{{out}}

<pre>

{{libheader|Wren-fmt}}

{{libheader|Wren-math}}

import "/math" for Int

for (p1 in 2..61) {

if (Int.isPrime(p1)) carmichael.call(p1)

{{out}}

=={{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;

{ T(p1,p2,p3) } // return list of three primes in Carmichael number

]];

cs.pump(Console.println,fcn([(p1,p2,p3)]){

{{out}}

<pre>

=={{header|ZX Spectrum Basic}}==

{{trans|C}}

20 LET n=p: GO SUB 1000

30 IF NOT n THEN GO TO 200

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