Rosetta Code

Erdös-Selfridge categorization of primes: Difference between revisions

Page Discussion

Erdös-Selfridge categorization of primes (view source)

Revision as of 10:26, 27 August 2022

468 bytes added ,  1 year ago
m
syntax highlighting fixup automation
m (→‎{{header|J}}: grammar)
m (syntax highlighting fixup automation)
Line 7:
=={{header|C++}}==
{{libheader|Primesieve}}
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <cassert>
#include <iomanip>
Line 101:
<< " count = " << v.size() << '\n';
}
}</langsyntaxhighlight>
 
{{out}}
Line 149:
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<langsyntaxhighlight lang="fsharp">
// Erdös-Selfridge categorization of primes. Nigel Galloway: April 12th., 2022
let rec fG n g=match n,g with ((_,1),_)|(_,[])->n |((_,p),h::_) when h>p->n |((p,q),h::_) when q%h=0->fG (p,q/h) g |(_,_::g)->fG n g
Line 155:
fN 200|>Seq.iteri(fun n g->printfn "Category %d: %A" (n+1) g)
fN 1000000|>Seq.iteri(fun n g->printfn "Category %d: first->%d last->%d count->%d" (n+1) (List.head g) (List.last g) (
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 191:
=={{header|Factor}}==
{{works with|Factor|0.99 2022-04-03}}
<langsyntaxhighlight lang="factor">USING: assocs combinators formatting grouping grouping.extras io
kernel math math.primes math.primes.factors math.statistics
prettyprint sequences sequences.deep ;
Line 224:
 
200 categories categories... nl
1,000,000 categories categories.</langsyntaxhighlight>
{{out}}
<pre>
Line 266:
{{trans|Wren}}
{{libheader|Go-rcu}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 345:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 354:
=={{header|J}}==
 
Implementation: <langsyntaxhighlight Jlang="j">pcat=: {{ assert. 1 p: y
1+>./0,pcat(q:1+y)-.2 3
}}M."0</langsyntaxhighlight>
 
Explanation: this is a recursive function defined only on primes. We memoize it for good performance.
Line 363:
 
First 200 primes -- category is in left box, primes are in right box:
<langsyntaxhighlight Jlang="j"> (,.~<@#\) (</.~ pcat) p:i.200
┌─┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│1│2 3 5 7 11 17 23 31 47 53 71 107 127 191 383 431 647 863 971 1151 │
Line 374:
├─┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│5│1021 │
└─┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘</langsyntaxhighlight>
 
First million primes, first column is category, second column is first prime in that category, third column is last prime in that category, final column is count of primes in that category:
 
<langsyntaxhighlight Jlang="j"> (,.~#\) (({.,{:,#)/.~ pcat) p:i.1e6
1 2 10616831 46
2 13 15482669 10497
Line 389:
9 532801 15472811 363
10 1065601 15472321 28
11 8524807 8524807 1</langsyntaxhighlight>
 
=={{header|Java}}==
Uses the PrimeGenerator class from [[Extensible prime generator#Java]].
<langsyntaxhighlight lang="java">import java.util.*;
 
public class ErdosSelfridge {
Line 469:
return Arrays.binarySearch(primes, prime);
}
}</langsyntaxhighlight>
 
{{out}}
Line 517:
=={{header|Julia}}==
{{trans|Raku}}
<langsyntaxhighlight lang="julia">using Primes
 
primefactors(n) = collect(keys(factor(n)))
Line 555:
 
testES(200, 1_000_000)
</langsyntaxhighlight>{{out}}
<pre>
First 200 primes by Erdös-Selfridge categories:
Line 579:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">ClearAll[SpecialPrimeFactors]
SpecialPrimeFactors[p_Integer] := FactorInteger[p + 1][[All, 1]]
 
Line 625:
TableForm[{First[#], Last[#], Length[#]} & /@ Rest[cs],
TableHeadings -> {Automatic, {"First", "Last", "Count"}},
TableAlignments -> Right]</langsyntaxhighlight>
{{out}}
<pre>
Line 679:
{{trans|Raku}}
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
Line 714:
printf "Category %2d: first: %9s last: %10s count: %s\n",
map { comma $_ } $_, (sort {$a <=> $b} @{$es{$_}})[0, -1], scalar @{$es{$_}}
for sort {$a <=> $b} keys %es;</langsyntaxhighlight>
{{out}}
<pre>First 200 primes, Erdös-Selfridge categorized:
Line 739:
{{libheader|Phix/online}}
You can run this online [http://phix.x10.mx/p2js/esprimes.htm here] (but expect a blank screen for about 20s)
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">escache</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
Line 791:
<span style="color: #000000;">categorise</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1e6</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 820:
=={{header|Raku}}==
 
<syntaxhighlight lang="raku" perl6line>use Prime::Factor;
use Lingua::EN::Numbers;
use Math::Primesieve;
Line 846:
say "\nSummary of first { cardinal $upto } primes; Erdös-Selfridge categorized:";
printf "Category %2d: first: %9s last: %10s count: %s\n", ++$, |(.[0], .[*-1], .elems).map: &comma
for $sieve.n-primes($upto).categorize( &Erdös-Selfridge ).sort(+*.key)».value;</langsyntaxhighlight>
{{out}}
<pre>First two hundred primes; Erdös-Selfridge categorized:
Line 869:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">// [dependencies]
// primal = "0.3"
 
Line 966:
);
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,013:
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func Erdös_Selfridge_class(n, s=1) is cached {
var f = factor_exp(n+s)
f.last.head > 3 || return 1
Line 1,027:
1e6.pn_primes.group_by(Erdös_Selfridge_class).sort_by{.to_i}.each_2d {|k,v|
printf("Category %2d: first: %9s last: %10s count: %s\n", k, v.first, v.last, v.len)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,055:
{{libheader|Wren-fmt}}
Runs in about 23.5 seconds.
<langsyntaxhighlight lang="ecmascript">import "./math" for Int
import "./fmt" for Fmt
 
Line 1,108:
Fmt.print("Category $-2d: First = $7d Last = $8d Count = $6d", c, e[0], e[-1], e.count)
}
}</langsyntaxhighlight>
 
{{out}}
Thundergnat
10,327

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/327476"