Carmichael 3 strong pseudoprimes: Difference between revisions
m
Automated syntax highlighting fixup (second round - minor fixes)
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
Thundergnat (talk | contribs) m (Automated syntax highlighting fixup (second round - minor fixes)) |
||
Line 33:
[[Chernick's Carmichael numbers]]
<br><br>
=={{header|11l}}==
{{trans|D}}
<syntaxhighlight lang="11l">F mod_(n, m)
R ((n % m) + m) % m
Line 88 ⟶ 87:
61 x 3361 x 4021
</pre>
=={{header|Ada}}==
Uses the Miller_Rabin package from
[[Miller-Rabin primality test#ordinary integers]].
<syntaxhighlight lang=
procedure Nemesis is
Line 147 ⟶ 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 #
PROC sieve = ( REF[]BOOL s )VOID:
BEGIN
Line 221 ⟶ 218:
61 3361 4021
</pre>
=={{header|AWK}}==
<syntaxhighlight lang=
# syntax: GAWK -f CARMICHAEL_3_STRONG_PSEUDOPRIMES.AWK
# converted from C
Line 341 ⟶ 337:
69 numbers
</pre>
=={{header|BASIC256}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang=
for i = 3 to max_sieve step 2
isprime[i] = 1
Line 383 ⟶ 377:
end
</syntaxhighlight>
=={{header|C}}==
<syntaxhighlight lang=
#include <stdio.h>
Line 454 ⟶ 446:
61 3361 4021
</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <iomanip>
#include <iostream>
Line 583 ⟶ 574:
61 x 3361 x 4021 = 824389441
</pre>
=={{header|Clojure}}==
<syntaxhighlight lang="lisp">
(ns example
(:gen-class))
Line 688 ⟶ 678:
</pre>
=={{header|D}}==
<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 ⟶ 782:
61 x 241 x 421
61 x 3361 x 4021</pre>
=={{header|EchoLisp}}==
<syntaxhighlight lang="scheme">
;; 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 ⟶ 800:
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="scheme">
(charms 3)
💥 561 = 3 x 11 x 17
Line 836 ⟶ 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#)]
<syntaxhighlight lang="fsharp">
// 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 ⟶ 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
sequences ;
IN: rosetta-code.carmichael
Line 1,019 ⟶ 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=
INTEGER N !Despite this intimidating allowance of 32 bits...
INTEGER F !A possible factor.
Line 1,139 ⟶ 1,124:
61 3361 4021 824389441
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">' version 17-10-2016
' compile with: fbc -s console
Line 1,270 ⟶ 1,254:
61 * 241 * 421
61 * 3361 * 4021</pre>
=={{header|Go}}==
<syntaxhighlight lang="go">package main
import "fmt"
Line 1,397 ⟶ 1,380:
61 3361 4021 824389441
</pre>
=={{header|Haskell}}==
{{trans|Ruby}}
Line 1,403 ⟶ 1,385:
{{Works with|GHC|7.4.1}}
{{Works with|primes|0.2.1.0}}
<syntaxhighlight lang="haskell">#!/usr/bin/runhaskell
import Data.Numbers.Primes
Line 1,493 ⟶ 1,475:
(61,3361,4021)
</pre>
=={{header|Icon}} and {{header|Unicon}}==
The following works in both languages.
<syntaxhighlight lang="unicon">link "factors"
procedure main(A)
Line 1,554 ⟶ 1,535:
->
</pre>
=={{header|J}}==
<syntaxhighlight lang=
q =: (,"0 1~ >:@i.@<:@+/"1)&.>@(,&.>"0 1~ >:@i.)&.>@I.@(1&p:@i.)@>:
f1 =: (0: = {. | <:@{: * 1&{ + {:) *. ((1&{ | -@*:@{:) = 1&{ | {.)
Line 1,636 ⟶ 1,616:
61 3361 4021
</pre>
=={{header|Java}}==
{{trans|D}}
<syntaxhighlight lang="java">public class Test {
static int mod(int n, int m) {
Line 1,747 ⟶ 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
function carmichael(pmax::Integer)
Line 1,775 ⟶ 1,753:
'''Main'''
<syntaxhighlight lang="julia">hi = 61
car = carmichael(hi)
Line 1,843 ⟶ 1,821:
42 results in total.</pre>
=={{header|Kotlin}}==
{{trans|D}}
<syntaxhighlight lang="scala">fun Int.isPrime(): Boolean {
return when {
this == 2 -> true
Line 1,884 ⟶ 1,861:
{{out}}
See D output.
=={{header|Lua}}==
<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 ⟶ 1,974:
61 × 3361 × 4021 = 824389441
69 found.</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<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 ⟶ 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
func isPrime(n: int64): bool =
Line 2,114 ⟶ 2,088:
61 × 3361 × 4021 = 824389441
</pre>
=={{header|PARI/GP}}==
<syntaxhighlight lang="parigp">f(p)={
my(v=List(),q,r);
for(h=2,p-1,
Line 2,130 ⟶ 2,103:
{{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}}
<syntaxhighlight lang="perl">use ntheory qw/forprimes is_prime vecprod/;
forprimes { my $p = $_;
Line 2,162 ⟶ 2,134:
61 x 3361 x 4021 = 824389441
</pre>
=={{header|Phix}}==
<!--<syntaxhighlight lang=
<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,204 ⟶ 2,175:
69 Carmichael numbers found
</pre>
=={{header|PicoLisp}}==
<syntaxhighlight lang=
(% (+ Y (% X Y)) Y) )
Line 2,246 ⟶ 2,216:
(bye)</syntaxhighlight>
=={{header|PL/I}}==
<syntaxhighlight lang=
declare (Prime1, Prime2, Prime3, h3, d) fixed binary (31);
Line 2,371 ⟶ 2,340:
61 x 3361 x 4021
</pre>
=={{header|Prolog}}==
<syntaxhighlight lang="prolog">
show(Limit) :-
forall(
Line 2,522 ⟶ 2,490:
true.
</pre>
=={{header|Python}}==
<syntaxhighlight lang="python">class Isprime():
'''
Extensible sieve of Eratosthenes
Line 2,610 ⟶ 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}}==
<syntaxhighlight lang="racket">
#lang racket
(require math)
Line 2,631 ⟶ 2,597:
</syntaxhighlight>
Output:
<syntaxhighlight lang="racket">
(3 11 17 => 561)
(5 29 73 => 10585)
Line 2,695 ⟶ 2,661:
(61 3361 4021 => 824389441)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{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" line>for (2..67).grep: *.is-prime -> \Prime1 {
for 1 ^..^ Prime1 -> \h3 {
my \g = h3 + Prime1;
Line 2,788 ⟶ 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 ⟶ 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). */
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 ⟶ 2,830:
──────── 8716 Carmichael numbers found.
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
# Project : Carmichael 3 strong pseudoprimes
Line 2,988 ⟶ 2,951:
61 3361 4021 824389441
</pre>
=={{header|Ruby}}==
{{works with|Ruby|1.9}}
<syntaxhighlight lang="ruby"># Generate Charmichael Numbers
require 'prime'
Line 3,098 ⟶ 3,060:
61 x 3361 x 4021
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">
fn is_prime(n: i64) -> bool {
if n > 1 {
Line 3,167 ⟶ 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";
const func boolean: isPrime (in integer: number) is func
Line 3,292 ⟶ 3,252:
61 * 3361 * 4021 = 824389441
</pre>
=={{header|Sidef}}==
{{trans|Perl}}
<syntaxhighlight lang="ruby">func forprimes(a, b, callback) {
for (a = (a-1 -> next_prime); a <= b; a.next_prime!) {
callback(a)
Line 3,329 ⟶ 3,288:
61 x 3361 x 4021 = 824389441
</pre>
=={{header|Swift}}==
{{trans|Rust}}
<syntaxhighlight lang="swift">import Foundation
extension BinaryInteger {
Line 3,417 ⟶ 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}} {
set carmichaels {}
for {set p1 2} {$p1 <= $limit} {incr p1} {
Line 3,444 ⟶ 3,401:
}</syntaxhighlight>
Demonstrating:
<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 ⟶ 3,479:
61 x 3361 x 4021 = 824389441
</pre>
=={{header|Vala}}==
{{trans|D}}
<syntaxhighlight lang="vala">long mod(long n, long m) {
return ((n % m) + m) % m;
}
Line 3,659 ⟶ 3,615:
61 × 3361 × 4021 = 824389441
</pre>
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="ecmascript">import "/fmt" for Fmt
import "/math" for Int
Line 3,771 ⟶ 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
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 ⟶ 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:");
cs.pump(Console.println,fcn([(p1,p2,p3)]){
"%2d * %4d * %5d = %d".fmt(p1,p2,p3,p1*p2*p3) });</syntaxhighlight>
Line 3,805 ⟶ 3,759:
61 * 3361 * 4021 = 824389441
</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
| |||