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

Content added Content deleted
m (→‎{{header|J}}: grammar)
m (syntax highlighting fixup automation)
Line 7: Line 7:
=={{header|C++}}==
=={{header|C++}}==
{{libheader|Primesieve}}
{{libheader|Primesieve}}
<lang cpp>#include <algorithm>
<syntaxhighlight lang="cpp">#include <algorithm>
#include <cassert>
#include <cassert>
#include <iomanip>
#include <iomanip>
Line 101: Line 101:
<< " count = " << v.size() << '\n';
<< " count = " << v.size() << '\n';
}
}
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 149: Line 149:
=={{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#)]
<lang fsharp>
<syntaxhighlight lang="fsharp">
// Erdös-Selfridge categorization of primes. Nigel Galloway: April 12th., 2022
// 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
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: Line 155:
fN 200|>Seq.iteri(fun n g->printfn "Category %d: %A" (n+1) g)
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) (
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}}
{{out}}
<pre>
<pre>
Line 191: Line 191:
=={{header|Factor}}==
=={{header|Factor}}==
{{works with|Factor|0.99 2022-04-03}}
{{works with|Factor|0.99 2022-04-03}}
<lang factor>USING: assocs combinators formatting grouping grouping.extras io
<syntaxhighlight lang="factor">USING: assocs combinators formatting grouping grouping.extras io
kernel math math.primes math.primes.factors math.statistics
kernel math math.primes math.primes.factors math.statistics
prettyprint sequences sequences.deep ;
prettyprint sequences sequences.deep ;
Line 224: Line 224:


200 categories categories... nl
200 categories categories... nl
1,000,000 categories categories.</lang>
1,000,000 categories categories.</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 266: Line 266:
{{trans|Wren}}
{{trans|Wren}}
{{libheader|Go-rcu}}
{{libheader|Go-rcu}}
<lang go>package main
<syntaxhighlight lang="go">package main


import (
import (
Line 345: Line 345:
}
}
}
}
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 354: Line 354:
=={{header|J}}==
=={{header|J}}==


Implementation: <lang J>pcat=: {{ assert. 1 p: y
Implementation: <syntaxhighlight lang="j">pcat=: {{ assert. 1 p: y
1+>./0,pcat(q:1+y)-.2 3
1+>./0,pcat(q:1+y)-.2 3
}}M."0</lang>
}}M."0</syntaxhighlight>


Explanation: this is a recursive function defined only on primes. We memoize it for good performance.
Explanation: this is a recursive function defined only on primes. We memoize it for good performance.
Line 363: Line 363:


First 200 primes -- category is in left box, primes are in right box:
First 200 primes -- category is in left box, primes are in right box:
<lang J> (,.~<@#\) (</.~ pcat) p:i.200
<syntaxhighlight lang="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 │
│1│2 3 5 7 11 17 23 31 47 53 71 107 127 191 383 431 647 863 971 1151 │
Line 374: Line 374:
├─┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
├─┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│5│1021 │
│5│1021 │
└─┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘</lang>
└─┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘</syntaxhighlight>


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


<lang J> (,.~#\) (({.,{:,#)/.~ pcat) p:i.1e6
<syntaxhighlight lang="j"> (,.~#\) (({.,{:,#)/.~ pcat) p:i.1e6
1 2 10616831 46
1 2 10616831 46
2 13 15482669 10497
2 13 15482669 10497
Line 389: Line 389:
9 532801 15472811 363
9 532801 15472811 363
10 1065601 15472321 28
10 1065601 15472321 28
11 8524807 8524807 1</lang>
11 8524807 8524807 1</syntaxhighlight>


=={{header|Java}}==
=={{header|Java}}==
Uses the PrimeGenerator class from [[Extensible prime generator#Java]].
Uses the PrimeGenerator class from [[Extensible prime generator#Java]].
<lang java>import java.util.*;
<syntaxhighlight lang="java">import java.util.*;


public class ErdosSelfridge {
public class ErdosSelfridge {
Line 469: Line 469:
return Arrays.binarySearch(primes, prime);
return Arrays.binarySearch(primes, prime);
}
}
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 517: Line 517:
=={{header|Julia}}==
=={{header|Julia}}==
{{trans|Raku}}
{{trans|Raku}}
<lang julia>using Primes
<syntaxhighlight lang="julia">using Primes


primefactors(n) = collect(keys(factor(n)))
primefactors(n) = collect(keys(factor(n)))
Line 555: Line 555:


testES(200, 1_000_000)
testES(200, 1_000_000)
</lang>{{out}}
</syntaxhighlight>{{out}}
<pre>
<pre>
First 200 primes by Erdös-Selfridge categories:
First 200 primes by Erdös-Selfridge categories:
Line 579: Line 579:


=={{header|Mathematica}}/{{header|Wolfram Language}}==
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<lang Mathematica>ClearAll[SpecialPrimeFactors]
<syntaxhighlight lang="mathematica">ClearAll[SpecialPrimeFactors]
SpecialPrimeFactors[p_Integer] := FactorInteger[p + 1][[All, 1]]
SpecialPrimeFactors[p_Integer] := FactorInteger[p + 1][[All, 1]]


Line 625: Line 625:
TableForm[{First[#], Last[#], Length[#]} & /@ Rest[cs],
TableForm[{First[#], Last[#], Length[#]} & /@ Rest[cs],
TableHeadings -> {Automatic, {"First", "Last", "Count"}},
TableHeadings -> {Automatic, {"First", "Last", "Count"}},
TableAlignments -> Right]</lang>
TableAlignments -> Right]</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 679: Line 679:
{{trans|Raku}}
{{trans|Raku}}
{{libheader|ntheory}}
{{libheader|ntheory}}
<lang perl>use strict;
<syntaxhighlight lang="perl">use strict;
use warnings;
use warnings;
use feature 'say';
use feature 'say';
Line 714: Line 714:
printf "Category %2d: first: %9s last: %10s count: %s\n",
printf "Category %2d: first: %9s last: %10s count: %s\n",
map { comma $_ } $_, (sort {$a <=> $b} @{$es{$_}})[0, -1], scalar @{$es{$_}}
map { comma $_ } $_, (sort {$a <=> $b} @{$es{$_}})[0, -1], scalar @{$es{$_}}
for sort {$a <=> $b} keys %es;</lang>
for sort {$a <=> $b} keys %es;</syntaxhighlight>
{{out}}
{{out}}
<pre>First 200 primes, Erdös-Selfridge categorized:
<pre>First 200 primes, Erdös-Selfridge categorized:
Line 739: Line 739:
{{libheader|Phix/online}}
{{libheader|Phix/online}}
You can run this online [http://phix.x10.mx/p2js/esprimes.htm here] (but expect a blank screen for about 20s)
You can run this online [http://phix.x10.mx/p2js/esprimes.htm here] (but expect a blank screen for about 20s)
<!--<lang Phix>(phixonline)-->
<!--<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: #004080;">sequence</span> <span style="color: #000000;">escache</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</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: 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: #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>
<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>
<!--</lang>-->
<!--</syntaxhighlight>-->
{{out}}
{{out}}
<pre>
<pre>
Line 820: Line 820:
=={{header|Raku}}==
=={{header|Raku}}==


<lang perl6>use Prime::Factor;
<syntaxhighlight lang="raku" line>use Prime::Factor;
use Lingua::EN::Numbers;
use Lingua::EN::Numbers;
use Math::Primesieve;
use Math::Primesieve;
Line 846: Line 846:
say "\nSummary of first { cardinal $upto } primes; Erdös-Selfridge categorized:";
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
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;</lang>
for $sieve.n-primes($upto).categorize( &Erdös-Selfridge ).sort(+*.key)».value;</syntaxhighlight>
{{out}}
{{out}}
<pre>First two hundred primes; Erdös-Selfridge categorized:
<pre>First two hundred primes; Erdös-Selfridge categorized:
Line 869: Line 869:


=={{header|Rust}}==
=={{header|Rust}}==
<lang rust>// [dependencies]
<syntaxhighlight lang="rust">// [dependencies]
// primal = "0.3"
// primal = "0.3"


Line 966: Line 966:
);
);
}
}
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 1,013: Line 1,013:


=={{header|Sidef}}==
=={{header|Sidef}}==
<lang ruby>func Erdös_Selfridge_class(n, s=1) is cached {
<syntaxhighlight lang="ruby">func Erdös_Selfridge_class(n, s=1) is cached {
var f = factor_exp(n+s)
var f = factor_exp(n+s)
f.last.head > 3 || return 1
f.last.head > 3 || return 1
Line 1,027: Line 1,027:
1e6.pn_primes.group_by(Erdös_Selfridge_class).sort_by{.to_i}.each_2d {|k,v|
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)
printf("Category %2d: first: %9s last: %10s count: %s\n", k, v.first, v.last, v.len)
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 1,055: Line 1,055:
{{libheader|Wren-fmt}}
{{libheader|Wren-fmt}}
Runs in about 23.5 seconds.
Runs in about 23.5 seconds.
<lang ecmascript>import "./math" for Int
<syntaxhighlight lang="ecmascript">import "./math" for Int
import "./fmt" for Fmt
import "./fmt" for Fmt


Line 1,108: Line 1,108:
Fmt.print("Category $-2d: First = $7d Last = $8d Count = $6d", c, e[0], e[-1], e.count)
Fmt.print("Category $-2d: First = $7d Last = $8d Count = $6d", c, e[0], e[-1], e.count)
}
}
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Retrieved from "https://rosettacode.org/wiki/Erdös-Selfridge_categorization_of_primes"