Fermat pseudoprimes: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: removed shorten()) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 55: | Line 55: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find some Fermat pseudo primes: x is a Fermat pseudoprime in base a # |
||
# if a^(x-1) - 1 is divisible by x and x is not prime # |
# if a^(x-1) - 1 is divisible by x and x is not prime # |
||
Line 133: | Line 133: | ||
print( ( newline ) ) |
print( ( newline ) ) |
||
OD |
OD |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 160: | Line 160: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Fermat pseudoprimes. Nigel Galloway: August 17th., 2022 |
// Fermat pseudoprimes. Nigel Galloway: August 17th., 2022 |
||
let fp(a:int)=let a=bigint a in primesI()|>Seq.pairwise|>Seq.collect(fun(n,g)->seq{for n in n+1I..g-1I do if bigint.ModPow(a,n-1I,n)=1I then yield n}) |
let fp(a:int)=let a=bigint a in primesI()|>Seq.pairwise|>Seq.collect(fun(n,g)->seq{for n in n+1I..g-1I do if bigint.ModPow(a,n-1I,n)=1I then yield n}) |
||
{1..20}|>Seq.iter(fun n->printf $"Base %2d{n} - Up to 50000: %5d{fp n|>Seq.takeWhile((>=)50000I)|>Seq.length} First 20: ("; fp n|>Seq.take 20|>Seq.iter(printf "%A "); printfn ")") |
{1..20}|>Seq.iter(fun n->printf $"Base %2d{n} - Up to 50000: %5d{fp n|>Seq.takeWhile((>=)50000I)|>Seq.length} First 20: ("; fp n|>Seq.take 20|>Seq.iter(printf "%A "); printfn ")") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 191: | Line 191: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="ruby">using Primes |
||
ispseudo(n, base) = !isprime(n) && BigInt(base)^(n - 1) % n == 1 |
ispseudo(n, base) = !isprime(n) && BigInt(base)^(n - 1) % n == 1 |
||
Line 199: | Line 199: | ||
println("Base ", lpad(b, 2), " up to 50000: ", lpad(length(pseudos), 5), " First 20: ", pseudos[1:20]) |
println("Base ", lpad(b, 2), " up to 50000: ", lpad(length(pseudos), 5), " First 20: ", pseudos[1:20]) |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Base 1 up to 50000: 44866 First 20: [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32] |
Base 1 up to 50000: 44866 First 20: [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32] |
||
Line 224: | Line 224: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
||
Line 258: | Line 258: | ||
<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;">"%2d: %s %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">})</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;">"%2d: %s %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">})</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre style="font-size: 12px"> |
<pre style="font-size: 12px"> |
||
Line 285: | Line 285: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>use List::Divvy; |
||
for 1..20 -> $base { |
for 1..20 -> $base { |
||
my @pseudo = lazy (2..*).hyper.grep: { !.is-prime && (1 == expmod $base, $_ - 1, $_) } |
my @pseudo = lazy (2..*).hyper.grep: { !.is-prime && (1 == expmod $base, $_ - 1, $_) } |
||
Line 291: | Line 291: | ||
say $base.fmt("Base %2d - Up to $threshold: ") ~ (+@pseudo.&upto: $threshold).fmt('%5d') |
say $base.fmt("Base %2d - Up to $threshold: ") ~ (+@pseudo.&upto: $threshold).fmt('%5d') |
||
~ " First 20: " ~ @pseudo[^20].gist |
~ " First 20: " ~ @pseudo[^20].gist |
||
}</ |
}</syntaxhighlight> |
||
<pre style="font-size:90%;">Base 1 - Up to 100000: 90407 First 20: (4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32) |
<pre style="font-size:90%;">Base 1 - Up to 100000: 90407 First 20: (4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32) |
||
Base 2 - Up to 100000: 78 First 20: (341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 8321) |
Base 2 - Up to 100000: 78 First 20: (341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 8321) |
||
Line 317: | Line 317: | ||
{{libheader|Wren-gmp}} |
{{libheader|Wren-gmp}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="ecmascript">import "./math" for Int |
||
import "./gmp" for Mpz |
import "./gmp" for Mpz |
||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
Line 360: | Line 360: | ||
} |
} |
||
System.print() |
System.print() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |