Carmichael 3 strong pseudoprimes: Difference between revisions

Line 33:

[[Chernick's Carmichael numbers]]

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

<syntaxhighlight lang=11l>F mod_(n, m)

<syntaxhighlight lang="11l">F mod_(n, m)

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

Line 88:

Line 87:

61 x 3361 x 4021

</pre>

=={{header|Ada}}==

Uses the Miller_Rabin package from

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

<syntaxhighlight lang=~~Ada~~>with Ada.Text_IO, Miller_Rabin;

<syntaxhighlight lang="ada">with Ada.Text_IO, Miller_Rabin;

procedure Nemesis is

Line 147:

Line 145:

61 * 241 * 421 = 6189121

61 * 3361 * 4021 = 824389441</pre>

=={{header|ALGOL 68}}==

Uses the Sieve of Eratosthenes code from the Smith Numbers task with an increased upper-bound (included here for convenience).

<syntaxhighlight lang=algol68># sieve of Eratosthene: sets s[i] to TRUE if i is prime, FALSE otherwise #

<syntaxhighlight lang="algol68"># sieve of Eratosthene: sets s[i] to TRUE if i is prime, FALSE otherwise #

PROC sieve = ( REF[]BOOL s )VOID:

BEGIN

Line 221:

Line 218:

61 3361 4021

</pre>

=={{header|AWK}}==

# syntax: GAWK -f CARMICHAEL_3_STRONG_PSEUDOPRIMES.AWK

# converted from C

Line 341:

Line 337:

69 numbers

</pre>

=={{header|BASIC256}}==

for i = 3 to max_sieve step 2

isprime[i] = 1

Line 383:

Line 377:

end

</syntaxhighlight>

=={{header|C}}==

#include <stdio.h>

Line 454:

Line 446:

61 3361 4021

</pre>

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

<syntaxhighlight lang=cpp>#include <iomanip>

<syntaxhighlight lang="cpp">#include <iomanip>

#include <iostream>

Line 583:

Line 574:

61 x 3361 x 4021 = 824389441

</pre>

=={{header|Clojure}}==

(ns example

(:gen-class))

Line 688:

Line 678:

</pre>

=={{header|D}}==

<syntaxhighlight lang=d>enum mod = (in int n, in int m) pure nothrow @nogc=> ((n % m) + m) % m;

<syntaxhighlight lang="d">enum mod = (in int n, in int m) pure nothrow @nogc=> ((n % m) + m) % m;

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

Line 793:

Line 782:

61 x 241 x 421

61 x 3361 x 4021</pre>

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

Line 800:

</syntaxhighlight>

(charms 3)

💥 561 = 3 x 11 x 17

Line 836:

Line 824:

💥 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 921:

Line 908:

61 x 3361 x 4021 = 824389441

</pre>

=={{header|Factor}}==

Note the use of <code>rem</code> instead of <code>mod</code> when the remainder should always be positive.

<syntaxhighlight lang=factor>USING: formatting kernel locals math math.primes math.ranges

<syntaxhighlight lang="factor">USING: formatting kernel locals math math.primes math.ranges

sequences ;

IN: rosetta-code.carmichael

Line 1,019:

Line 1,005:

61 3361 4021

</pre>

=={{header|Fortran}}==

===Plan===

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... <syntaxhighlight lang=~~Fortran~~> LOGICAL FUNCTION ISPRIME(N) !Ad-hoc, since N is not going to be big...

So, using the double MOD approach (see the ''Discussion'') - which gives the same result for either style of MOD... <syntaxhighlight lang="fortran"> LOGICAL FUNCTION ISPRIME(N) !Ad-hoc, since N is not going to be big...

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

INTEGER F !A possible factor.

Line 1,139:

Line 1,124:

61 3361 4021 824389441

</pre>

=={{header|FreeBASIC}}==

<syntaxhighlight lang=freebasic>' version 17-10-2016

<syntaxhighlight lang="freebasic">' version 17-10-2016

' compile with: fbc -s console

Line 1,270:

Line 1,254:

61 * 241 * 421

61 * 3361 * 4021</pre>

=={{header|Go}}==

<syntaxhighlight lang=go>package main

<syntaxhighlight lang="go">package main

import "fmt"

Line 1,397:

Line 1,380:

61 3361 4021 824389441

</pre>

=={{header|Haskell}}==

Line 1,403:

Line 1,385:

<syntaxhighlight lang=haskell>#!/usr/bin/runhaskell

<syntaxhighlight lang="haskell">#!/usr/bin/runhaskell

import Data.Numbers.Primes

Line 1,493:

Line 1,475:

(61,3361,4021)

</pre>

=={{header|Icon}} and {{header|Unicon}}==

The following works in both languages.

<syntaxhighlight lang=unicon>link "factors"

<syntaxhighlight lang="unicon">link "factors"

procedure main(A)

Line 1,554:

Line 1,535:

->

</pre>

=={{header|J}}==

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

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

Line 1,636:

Line 1,616:

61 3361 4021

</pre>

=={{header|Java}}==

<syntaxhighlight lang=java>public class Test {

<syntaxhighlight lang="java">public class Test {

static int mod(int n, int m) {

Line 1,747:

Line 1,726:

61 x 241 x 421

61 x 3361 x 4021</pre>

=={{header|Julia}}==

This solution is a straightforward implementation of the algorithm of the Jameson paper cited in the task description. Just for fun, I use Julia's capacity to accommodate Unicode identifiers to match some of the paper's symbols to the variables used in the <tt>carmichael</tt> function.

'''Function'''

<syntaxhighlight lang=julia>using Primes

<syntaxhighlight lang="julia">using Primes

function carmichael(pmax::Integer)

Line 1,775:

Line 1,753:

'''Main'''

<syntaxhighlight lang=julia>hi = 61

<syntaxhighlight lang="julia">hi = 61

car = carmichael(hi)

Line 1,843:

Line 1,821:

42 results in total.</pre>

=={{header|Kotlin}}==

<syntaxhighlight lang=scala>fun Int.isPrime(): Boolean {

<syntaxhighlight lang="scala">fun Int.isPrime(): Boolean {

return when {

this == 2 -> true

Line 1,884:

Line 1,861:

See D output.

=={{header|Lua}}==

<syntaxhighlight lang=lua>local function isprime(n)

<syntaxhighlight lang="lua">local function isprime(n)

if n < 2 then return false end

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

Line 1,998:

Line 1,974:

61 × 3361 × 4021 = 824389441

69 found.</pre>

=={{header|Mathematica}} / {{header|Wolfram Language}}==

<syntaxhighlight lang=mathematica>Cases[Cases[

<syntaxhighlight lang="mathematica">Cases[Cases[

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,008:

Line 1,983:

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

Mod[p2 p3, p1 - 1] == 1 :> Print[p1, "*", p2, "*", p3]]</syntaxhighlight>

=={{header|Nim}}==

{{trans|Vala}} with some modifications

<syntaxhighlight lang=nim>import strformat

<syntaxhighlight lang="nim">import strformat

func isPrime(n: int64): bool =

Line 2,114:

Line 2,088:

61 × 3361 × 4021 = 824389441

</pre>

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

<syntaxhighlight lang=parigp>f(p)={

<syntaxhighlight lang="parigp">f(p)={

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

for(h=2,p-1,

Line 2,130:

Line 2,103:

=={{header|Perl}}==

<syntaxhighlight lang=perl>use ntheory qw/forprimes is_prime vecprod/;

<syntaxhighlight lang="perl">use ntheory qw/forprimes is_prime vecprod/;

forprimes { my $p = $_;

Line 2,162:

Line 2,134:

61 x 3361 x 4021 = 824389441

</pre>

=={{header|Phix}}==

with javascript_semantics

integer count = 0

Line 2,204:

Line 2,175:

69 Carmichael numbers found

</pre>

=={{header|PicoLisp}}==

<syntaxhighlight lang=~~PicoLisp~~>(de modulo (X Y)

<syntaxhighlight lang="picolisp">(de modulo (X Y)

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

Line 2,246:

Line 2,216:

(bye)</syntaxhighlight>

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

<syntaxhighlight lang=PL/I>Carmichael: procedure options (main, reorder); /* 24 January 2014 */

<syntaxhighlight lang="pl/i">Carmichael: procedure options (main, reorder); /* 24 January 2014 */

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

Line 2,371:

Line 2,340:

61 x 3361 x 4021

</pre>

=={{header|Prolog}}==

show(Limit) :-

forall(

Line 2,522:

Line 2,490:

true.

</pre>

=={{header|Python}}==

<syntaxhighlight lang=python>class Isprime():

<syntaxhighlight lang="python">class Isprime():

'''

Extensible sieve of Eratosthenes

Line 2,610:

Line 2,577:

(61, 181, 5521), (61, 241, 421), (61, 271, 571), (61, 277, 2113), (61, 421, 12841),

(61, 541, 3001), (61, 661, 2521), (61, 1301, 19841), (61, 3361, 4021)</pre>

=={{header|Racket}}==

#lang racket

(require math)

Line 2,631:

Line 2,597:

</syntaxhighlight>

Output:

(3 11 17 => 561)

(5 29 73 => 10585)

Line 2,695:

Line 2,661:

(61 3361 4021 => 824389441)

</syntaxhighlight>

=={{header|Raku}}==

(formerly Perl 6)

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 line>for (2..67).grep: *.is-prime -> \Prime1 {

<syntaxhighlight lang="raku" line>for (2..67).grep: *.is-prime -> \Prime1 {

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

my \g = h3 + Prime1;

Line 2,788:

Line 2,753:

67 × 331 × 7393 == 163954561

67 × 331 × 463 == 10267951</pre>

=={{header|REXX}}==

Note that REXX's version of   '''modulus'''   (<big><code>'''//'''</code></big>)   is really a   ''remainder''   function.

Line 2,795:

Line 2,759:

Some code optimization was done, while not necessary for the small default number ('''61'''),   it was significant for larger numbers.

<syntaxhighlight lang=rexx>/*REXX program calculates Carmichael 3─strong pseudoprimes (up to and including N). */

<syntaxhighlight lang="rexx">/*REXX program calculates Carmichael 3─strong pseudoprimes (up to and including N). */

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,866:

Line 2,830:

──────── 8716 Carmichael numbers found.

</pre>

=={{header|Ring}}==

# Project : Carmichael 3 strong pseudoprimes

Line 2,988:

Line 2,951:

61 3361 4021 824389441

</pre>

=={{header|Ruby}}==

<syntaxhighlight lang=ruby># Generate Charmichael Numbers

<syntaxhighlight lang="ruby"># Generate Charmichael Numbers

require 'prime'

Line 3,098:

Line 3,060:

61 x 3361 x 4021

</pre>

=={{header|Rust}}==

fn is_prime(n: i64) -> bool {

if n > 1 {

Line 3,167:

Line 3,128:

(61, 3361, 4021)

</pre>

=={{header|Seed7}}==

The function [http://seed7.sourceforge.net/algorith/math.htm#isPrime isPrime] below is borrowed from the [http://seed7.sourceforge.net/algorith Seed7 algorithm collection].

<syntaxhighlight lang=seed7>$ include "seed7_05.s7i";

<syntaxhighlight lang="seed7">$ include "seed7_05.s7i";

const func boolean: isPrime (in integer: number) is func

Line 3,292:

Line 3,252:

61 * 3361 * 4021 = 824389441

</pre>

=={{header|Sidef}}==

<syntaxhighlight lang=ruby>func forprimes(a, b, callback) {

<syntaxhighlight lang="ruby">func forprimes(a, b, callback) {

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

callback(a)

Line 3,329:

Line 3,288:

61 x 3361 x 4021 = 824389441

</pre>

=={{header|Swift}}==

<syntaxhighlight lang=swift>import Foundation

<syntaxhighlight lang="swift">import Foundation

extension BinaryInteger {

Line 3,417:

Line 3,375:

(61, 241, 421)

(61, 3361, 4021)</pre>

=={{header|Tcl}}==

Using the primality tester from [[Miller-Rabin primality test#Tcl|the Miller-Rabin task]]...

<syntaxhighlight lang=tcl>proc carmichael {limit {rounds 10}} {

<syntaxhighlight lang="tcl">proc carmichael {limit {rounds 10}} {

set carmichaels {}

for {set p1 2} {$p1 <= $limit} {incr p1} {

Line 3,444:

Line 3,401:

}</syntaxhighlight>

Demonstrating:

<syntaxhighlight lang=tcl>set results [carmichael 61 2]

<syntaxhighlight lang="tcl">set results [carmichael 61 2]

puts "[expr {[llength $results]/4}] Carmichael numbers found"

foreach {p1 p2 p3 c} $results {

Line 3,522:

Line 3,479:

61 x 3361 x 4021 = 824389441

</pre>

=={{header|Vala}}==

<syntaxhighlight lang=vala>long mod(long n, long m) {

<syntaxhighlight lang="vala">long mod(long n, long m) {

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

}

Line 3,659:

Line 3,615:

61 × 3361 × 4021 = 824389441

</pre>

=={{header|Wren}}==

<syntaxhighlight lang=ecmascript>import "/fmt" for Fmt

<syntaxhighlight lang="ecmascript">import "/fmt" for Fmt

import "/math" for Int

Line 3,771:

Line 3,726:

61 3361 4021 824389441

</pre>

=={{header|zkl}}==

Using the Miller-Rabin primality test in lib GMP.

<syntaxhighlight lang=zkl>var BN=Import("zklBigNum"), bi=BN(0); // gonna recycle bi

<syntaxhighlight lang="zkl">var BN=Import("zklBigNum"), bi=BN(0); // gonna recycle bi

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,786:

Line 3,740:

]];

fcn mod(a,b) { m:=a%b; if(m<0) m+b else m }</syntaxhighlight>

<syntaxhighlight lang=zkl>cs.len().println(" Carmichael numbers found:");

<syntaxhighlight lang="zkl">cs.len().println(" Carmichael numbers found:");

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

"%2d * %4d * %5d = %d".fmt(p1,p2,p3,p1*p2*p3) });</syntaxhighlight>

Line 3,805:

Line 3,759:

61 * 3361 * 4021 = 824389441

</pre>

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

<syntaxhighlight lang=zxbasic>10 FOR p=2 TO 61

<syntaxhighlight lang="zxbasic">10 FOR p=2 TO 61

20 LET n=p: GO SUB 1000

30 IF NOT n THEN GO TO 200