I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Erdös-Selfridge categorization of primes

Erdös-Selfridge categorization of primes
You are encouraged to solve this task according to the task description, using any language you may know.

A prime p is in category 1 if the prime factors of p+1 are 2 and or 3. p is in category 2 if all the prime factors of p+1 are in category 1. p is in category g if all the prime factors of p+1 are in categories 1 to g-1.

The task is first to display the first 200 primes allocated to their category, then assign the first million primes to their category, displaying the smallest prime, the largest prime, and the count of primes allocated to each category.

## C++

Library: Primesieve
`#include <algorithm>#include <cassert>#include <iomanip>#include <iostream>#include <map>#include <vector> #include <primesieve.hpp> class erdos_selfridge {public:    explicit erdos_selfridge(int limit);    uint64_t get_prime(int index) const { return primes_[index].first; }    int get_category(int index); private:    std::vector<std::pair<uint64_t, int>> primes_;    size_t get_index(uint64_t prime) const;}; erdos_selfridge::erdos_selfridge(int limit) {    primesieve::iterator iter;    for (int i = 0; i < limit; ++i)        primes_.emplace_back(iter.next_prime(), 0);} int erdos_selfridge::get_category(int index) {    auto& pair = primes_[index];    if (pair.second != 0)        return pair.second;    int max_category = 0;    uint64_t n = pair.first + 1;    for (int i = 0; n > 1; ++i) {        uint64_t p = primes_[i].first;        if (p * p > n)            break;        int count = 0;        for (; n % p == 0; ++count)            n /= p;        if (count != 0) {            int category = (p <= 3) ? 1 : 1 + get_category(i);            max_category = std::max(max_category, category);        }    }    if (n > 1) {        int category = (n <= 3) ? 1 : 1 + get_category(get_index(n));        max_category = std::max(max_category, category);    }    pair.second = max_category;    return max_category;} size_t erdos_selfridge::get_index(uint64_t prime) const {    auto it = std::lower_bound(primes_.begin(), primes_.end(), prime,                               [](const std::pair<uint64_t, int>& p,                                  uint64_t n) { return p.first < n; });    assert(it != primes_.end());    assert(it->first == prime);    return std::distance(primes_.begin(), it);} auto get_primes_by_category(erdos_selfridge& es, int limit) {    std::map<int, std::vector<uint64_t>> primes_by_category;    for (int i = 0; i < limit; ++i) {        uint64_t prime = es.get_prime(i);        int category = es.get_category(i);        primes_by_category[category].push_back(prime);    }    return primes_by_category;} int main() {    const int limit1 = 200, limit2 = 1000000;     erdos_selfridge es(limit2);     std::cout << "First 200 primes:\n";    for (const auto& p : get_primes_by_category(es, limit1)) {        std::cout << "Category " << p.first << ":\n";        for (size_t i = 0, n = p.second.size(); i != n; ++i) {            std::cout << std::setw(4) << p.second[i]                      << ((i + 1) % 15 == 0 ? '\n' : ' ');        }        std::cout << "\n\n";    }     std::cout << "First 1,000,000 primes:\n";    for (const auto& p : get_primes_by_category(es, limit2)) {        const auto& v = p.second;        std::cout << "Category " << std::setw(2) << p.first << ": "                  << "first = " << std::setw(7) << v.front()                  << "  last = " << std::setw(8) << v.back()                  << "  count = " << v.size() << '\n';    }}`
Output:
```First 200 primes:
Category 1:
2    3    5    7   11   17   23   31   47   53   71  107  127  191  383
431  647  863  971 1151

Category 2:
13   19   29   41   43   59   61   67   79   83   89   97  101  109  131
137  139  149  167  179  197  199  211  223  229  239  241  251  263  269
271  281  283  293  307  317  349  359  367  373  419  433  439  449  461
479  499  503  509  557  563  577  587  593  599  619  641  643  659  709
719  743  751  761  769  809  827  839  881  919  929  953  967  991 1019
1033 1049 1069 1087 1103 1187 1223

Category 3:
37  103  113  151  157  163  173  181  193  227  233  257  277  311  331
337  347  353  379  389  397  401  409  421  457  463  467  487  491  521
523  541  547  569  571  601  607  613  631  653  683  701  727  733  773
787  797  811  821  829  853  857  859  877  883  911  937  947  983  997
1009 1013 1031 1039 1051 1061 1063 1091 1097 1117 1123 1153 1163 1171 1181
1193 1217

Category 4:
73  313  443  617  661  673  677  691  739  757  823  887  907  941  977
1093 1109 1129 1201 1213

Category 5:
1021

First 1,000,000 primes:
Category  1: first =       2  last = 10616831  count = 46
Category  2: first =      13  last = 15482669  count = 10497
Category  3: first =      37  last = 15485863  count = 201987
Category  4: first =      73  last = 15485849  count = 413891
Category  5: first =    1021  last = 15485837  count = 263109
Category  6: first =    2917  last = 15485857  count = 87560
Category  7: first =   15013  last = 15484631  count = 19389
Category  8: first =   49681  last = 15485621  count = 3129
Category  9: first =  532801  last = 15472811  count = 363
Category 10: first = 1065601  last = 15472321  count = 28
Category 11: first = 8524807  last =  8524807  count = 1
```

## F#

This task uses Extensible Prime Generator (F#)

` // Erdös-Selfridge categorization of primes. Nigel Galloway: April 12th., 2022let 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 glet fN g=Seq.unfold(fun(n,g)->let n,g=n|>List.map(fun n->fG n g)|>List.partition(fun(_,n)->n<>1) in let g=g|>List.map fst in if g=[] then None else Some(g,(n,g)))(primes32()|>Seq.take g|>Seq.map(fun n->(n,n+1))|>List.ofSeq,[2;3])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) ( `
Output:
```Category 1: [2; 3; 5; 7; 11; 17; 23; 31; 47; 53; 71; 107; 127; 191; 383; 431; 647; 863; 971;
1151]
Category 2: [13; 19; 29; 41; 43; 59; 61; 67; 79; 83; 89; 97; 101; 109; 131; 137; 139; 149;
167; 179; 197; 199; 211; 223; 229; 239; 241; 251; 263; 269; 271; 281; 283; 293;
307; 317; 349; 359; 367; 373; 419; 433; 439; 449; 461; 479; 499; 503; 509; 557;
563; 577; 587; 593; 599; 619; 641; 643; 659; 709; 719; 743; 751; 761; 769; 809;
827; 839; 881; 919; 929; 953; 967; 991; 1019; 1033; 1049; 1069; 1087; 1103;
1187; 1223]
Category 3: [37; 103; 113; 151; 157; 163; 173; 181; 193; 227; 233; 257; 277; 311; 331; 337;
347; 353; 379; 389; 397; 401; 409; 421; 457; 463; 467; 487; 491; 521; 523; 541;
547; 569; 571; 601; 607; 613; 631; 653; 683; 701; 727; 733; 773; 787; 797; 811;
821; 829; 853; 857; 859; 877; 883; 911; 937; 947; 983; 997; 1009; 1013; 1031;
1039; 1051; 1061; 1063; 1091; 1097; 1117; 1123; 1153; 1163; 1171; 1181; 1193;
1217]
Category 4: [73; 313; 443; 617; 661; 673; 677; 691; 739; 757; 823; 887; 907; 941; 977; 1093;
1109; 1129; 1201; 1213]
Category 5: [1021]

Category 1: first->2 last->10616831 count->46
Category 2: first->13 last->15482669 count->10497
Category 3: first->37 last->15485863 count->201987
Category 4: first->73 last->15485849 count->413891
Category 5: first->1021 last->15485837 count->263109
Category 6: first->2917 last->15485857 count->87560
Category 7: first->15013 last->15484631 count->19389
Category 8: first->49681 last->15485621 count->3129
Category 9: first->532801 last->15472811 count->363
Category 10: first->1065601 last->15472321 count->28
Category 11: first->8524807 last->8524807 count->1
```

## Factor

Works with: Factor version 0.99 2022-04-03
`USING: assocs combinators formatting grouping grouping.extras iokernel math math.primes math.primes.factors math.statisticsprettyprint sequences sequences.deep ; PREDICATE: >3 < integer 3 > ; GENERIC: depth ( seq -- n ) M: sequence depth    0 swap [ flatten1 [ 1 + ] dip ] to-fixed-point drop ; M: integer depth drop 1 ; MEMO: pfactors ( n -- seq ) 1 + factors ; : category ( m -- n )    [ dup >3? [ pfactors ] when ] deep-map depth ; : categories ( n -- assoc ) nprimes [ category ] collect-by ; : table. ( seq n -- )    [ "" pad-groups ] keep group simple-table. ; : categories... ( assoc -- )    [ [ "Category %d:\n" printf ] dip 15 table. ] assoc-each ; : row. ( category first last count -- )    "Category %d: first->%d last->%d count->%d\n" printf ; : categories. ( assoc -- )    [ [ minmax ] keep length row. ] assoc-each ; 200 categories categories... nl1,000,000 categories categories.`
Output:
```Category 1:
2   3   5   7   11   17 23 31 47 53 71 107 127 191 383
431 647 863 971 1151
Category 2:
13   19   29   41   43   59   61   67  79  83  89  97  101 109 131
137  139  149  167  179  197  199  211 223 229 239 241 251 263 269
271  281  283  293  307  317  349  359 367 373 419 433 439 449 461
479  499  503  509  557  563  577  587 593 599 619 641 643 659 709
719  743  751  761  769  809  827  839 881 919 929 953 967 991 1019
1033 1049 1069 1087 1103 1187 1223
Category 3:
37   103  113  151  157  163  173  181  193  227  233  257  277  311  331
337  347  353  379  389  397  401  409  421  457  463  467  487  491  521
523  541  547  569  571  601  607  613  631  653  683  701  727  733  773
787  797  811  821  829  853  857  859  877  883  911  937  947  983  997
1009 1013 1031 1039 1051 1061 1063 1091 1097 1117 1123 1153 1163 1171 1181
1193 1217
Category 4:
73   313  443  617  661  673 677 691 739 757 823 887 907 941 977
1093 1109 1129 1201 1213
Category 5:
1021

Category 1: first->2 last->10616831 count->46
Category 2: first->13 last->15482669 count->10497
Category 3: first->37 last->15485863 count->201987
Category 4: first->73 last->15485849 count->413891
Category 5: first->1021 last->15485837 count->263109
Category 6: first->2917 last->15485857 count->87560
Category 7: first->15013 last->15484631 count->19389
Category 8: first->49681 last->15485621 count->3129
Category 9: first->532801 last->15472811 count->363
Category 10: first->1065601 last->15472321 count->28
Category 11: first->8524807 last->8524807 count->1
```

## Go

Translation of: Wren
Library: Go-rcu
`package main import (    "fmt"    "math"    "rcu") var limit = int(math.Log(1e6) * 1e6 * 1.2) // should be more than enoughvar primes = rcu.Primes(limit) var prevCats = make(map[int]int) func cat(p int) int {    if v, ok := prevCats[p]; ok {        return v    }    pf := rcu.PrimeFactors(p + 1)    all := true    for _, f := range pf {        if f != 2 && f != 3 {            all = false            break        }    }    if all {        return 1    }    if p > 2 {        len := len(pf)        for i := len - 1; i >= 1; i-- {            if pf[i-1] == pf[i] {                pf = append(pf[:i], pf[i+1:]...)            }        }    }    for c := 2; c <= 11; c++ {        all := true        for _, f := range pf {            if cat(f) >= c {                all = false                break            }        }        if all {            prevCats[p] = c            return c        }    }    return 12} func main() {    es := make([][]int, 12)    fmt.Println("First 200 primes:\n")    for _, p := range primes[0:200] {        c := cat(p)        es[c-1] = append(es[c-1], p)    }    for c := 1; c <= 6; c++ {        if len(es[c-1]) > 0 {            fmt.Println("Category", c, "\b:")            fmt.Println(es[c-1])            fmt.Println()        }    }     fmt.Println("First million primes:\n")    for _, p := range primes[200:1e6] {        c := cat(p)        es[c-1] = append(es[c-1], p)    }    for c := 1; c <= 12; c++ {        e := es[c-1]        if len(e) > 0 {            format := "Category %-2d: First = %7d  Last = %8d  Count = %6d\n"            fmt.Printf(format, c, e[0], e[len(e)-1], len(e))        }    }}`
Output:
```Same as Wren example.
```

## Java

Uses the PrimeGenerator class from Extensible prime generator#Java.

`import java.util.*; public class ErdosSelfridge {    private int[] primes;    private int[] category;     public static void main(String[] args) {        ErdosSelfridge es = new ErdosSelfridge(1000000);         System.out.println("First 200 primes:");        for (var e : es.getPrimesByCategory(200).entrySet()) {            int category = e.getKey();            List<Integer> primes = e.getValue();            System.out.printf("Category %d:\n", category);            for (int i = 0, n = primes.size(); i != n; ++i)                System.out.printf("%4d%c", primes.get(i), (i + 1) % 15 == 0 ? '\n' : ' ');            System.out.printf("\n\n");        }         System.out.println("First 1,000,000 primes:");        for (var e : es.getPrimesByCategory(1000000).entrySet()) {            int category = e.getKey();            List<Integer> primes = e.getValue();            System.out.printf("Category %2d: first = %7d  last = %8d  count = %d\n", category,                              primes.get(0), primes.get(primes.size() - 1), primes.size());        }    }     private ErdosSelfridge(int limit) {        PrimeGenerator primeGen = new PrimeGenerator(100000, 200000);        List<Integer> primeList = new ArrayList<>();        for (int i = 0; i < limit; ++i)            primeList.add(primeGen.nextPrime());        primes = new int[primeList.size()];        for (int i = 0; i < primes.length; ++i)            primes[i] = primeList.get(i);        category = new int[primes.length];    }     private Map<Integer, List<Integer>> getPrimesByCategory(int limit) {        Map<Integer, List<Integer>> result = new TreeMap<>();        for (int i = 0; i < limit; ++i) {            var p = result.computeIfAbsent(getCategory(i), k -> new ArrayList<Integer>());            p.add(primes[i]);        }        return result;    }     private int getCategory(int index) {        if (category[index] != 0)            return category[index];        int maxCategory = 0;        int n = primes[index] + 1;        for (int i = 0; n > 1; ++i) {            int p = primes[i];            if (p * p > n)                break;            int count = 0;            for (; n % p == 0; ++count)                n /= p;            if (count != 0) {                int category = (p <= 3) ? 1 : 1 + getCategory(i);                maxCategory = Math.max(maxCategory, category);            }        }        if (n > 1) {            int category = (n <= 3) ? 1 : 1 + getCategory(getIndex(n));            maxCategory = Math.max(maxCategory, category);        }        category[index] = maxCategory;        return maxCategory;    }     private int getIndex(int prime) {       return Arrays.binarySearch(primes, prime);    }}`
Output:
```First 200 primes:
Category 1:
2    3    5    7   11   17   23   31   47   53   71  107  127  191  383
431  647  863  971 1151

Category 2:
13   19   29   41   43   59   61   67   79   83   89   97  101  109  131
137  139  149  167  179  197  199  211  223  229  239  241  251  263  269
271  281  283  293  307  317  349  359  367  373  419  433  439  449  461
479  499  503  509  557  563  577  587  593  599  619  641  643  659  709
719  743  751  761  769  809  827  839  881  919  929  953  967  991 1019
1033 1049 1069 1087 1103 1187 1223

Category 3:
37  103  113  151  157  163  173  181  193  227  233  257  277  311  331
337  347  353  379  389  397  401  409  421  457  463  467  487  491  521
523  541  547  569  571  601  607  613  631  653  683  701  727  733  773
787  797  811  821  829  853  857  859  877  883  911  937  947  983  997
1009 1013 1031 1039 1051 1061 1063 1091 1097 1117 1123 1153 1163 1171 1181
1193 1217

Category 4:
73  313  443  617  661  673  677  691  739  757  823  887  907  941  977
1093 1109 1129 1201 1213

Category 5:
1021

First 1,000,000 primes:
Category  1: first =       2  last = 10616831  count = 46
Category  2: first =      13  last = 15482669  count = 10497
Category  3: first =      37  last = 15485863  count = 201987
Category  4: first =      73  last = 15485849  count = 413891
Category  5: first =    1021  last = 15485837  count = 263109
Category  6: first =    2917  last = 15485857  count = 87560
Category  7: first =   15013  last = 15484631  count = 19389
Category  8: first =   49681  last = 15485621  count = 3129
Category  9: first =  532801  last = 15472811  count = 363
Category 10: first = 1065601  last = 15472321  count = 28
Category 11: first = 8524807  last =  8524807  count = 1
```

## Julia

Translation of: Raku
`using Primes primefactors(n) = collect(keys(factor(n))) function ErdösSelfridge(n)    highfactors = filter(>(3), primefactors(n + 1))    category = 1    while !isempty(highfactors)        highfactors = unique(reduce(vcat, [filter(>(3), primefactors(a + 1)) for a in highfactors]))        category += 1    end    return categoryend function testES(numshowprimes, numtotalprimes)    println("First \$numshowprimes primes by Erdös-Selfridge categories:")    dict = Dict{Int, Vector{Int}}(i => [] for i in 1:5)    for p in primes(prime(numshowprimes))        push!(dict[ErdösSelfridge(p)], p)    end    for cat in 1:5        println("\$cat => ", dict[cat])    end    dict2 = Dict{Int, Tuple{Int, Int, Int}}(i => (0, 0, 0) for i in 1:11)    println("\nTotals for first \$numtotalprimes primes by Erdös-Selfridge categories:")    for p in primes(prime(numtotalprimes))        cat = ErdösSelfridge(p)        fir, tot, las = dict2[cat]        fir == 0 && (fir = p)        dict2[cat] = (fir, tot + 1, p)    end    for cat in 1:11        first, total, last = dict2[cat]        println("Category", lpad(cat, 3), " => first:", lpad(first, 8), ", total:", lpad(total, 7), ", last:", last)    endend testES(200, 1_000_000) `
Output:
```First 200 primes by Erdös-Selfridge categories:
1 => [2, 3, 5, 7, 11, 17, 23, 31, 47, 53, 71, 107, 127, 191, 383, 431, 647, 863, 971, 1151]
2 => [13, 19, 29, 41, 43, 59, 61, 67, 79, 83, 89, 97, 101, 109, 131, 137, 139, 149, 167, 179, 197, 199, 211, 223, 229, 239, 241, 251, 263, 269, 271, 281, 283, 293, 307, 317, 349, 359, 367, 373, 419, 433, 439, 449, 461, 479, 499, 503, 509, 557, 563, 577, 587, 593, 599, 619, 641, 643, 659, 709, 719, 743, 751, 761, 769, 809, 827, 839, 881, 919, 929, 953, 967, 991, 1019, 1033, 1049, 1069, 1087, 1103, 1187, 1223]
3 => [37, 103, 113, 151, 157, 163, 173, 181, 193, 227, 233, 257, 277, 311, 331, 337, 347, 353, 379, 389, 397, 401, 409, 421, 457, 463, 467, 487, 491, 521, 523, 541, 547, 569, 571, 601, 607, 613, 631, 653, 683, 701, 727, 733, 773, 787, 797, 811, 821, 829, 853, 857, 859, 877, 883, 911, 937, 947, 983, 997, 1009, 1013, 1031, 1039, 1051, 1061, 1063, 1091, 1097, 1117, 1123, 1153, 1163, 1171, 1181, 1193, 1217]
4 => [73, 313, 443, 617, 661, 673, 677, 691, 739, 757, 823, 887, 907, 941, 977, 1093, 1109, 1129, 1201, 1213]
5 => [1021]

Totals for first 1000000 primes by Erdös-Selfridge categories:
Category  1 => first:       2, total:     46, last:10616831
Category  2 => first:      13, total:  10497, last:15482669
Category  3 => first:      37, total: 201987, last:15485863
Category  4 => first:      73, total: 413891, last:15485849
Category  5 => first:    1021, total: 263109, last:15485837
Category  6 => first:    2917, total:  87560, last:15485857
Category  7 => first:   15013, total:  19389, last:15484631
Category  8 => first:   49681, total:   3129, last:15485621
Category  9 => first:  532801, total:    363, last:15472811
Category 10 => first: 1065601, total:     28, last:15472321
Category 11 => first: 8524807, total:      1, last:8524807
```

## Perl

Translation of: Raku
Library: ntheory
`use strict;use warnings;use feature 'say';use List::Util 'max';use ntheory qw/factor/;use Primesieve qw(generate_primes); my @primes = (0, generate_primes (1, 10**8));my %cat = (2 => 1, 3 => 1); sub comma { reverse ((reverse shift) =~ s/(.{3})/\$1,/gr) =~ s/^,//r } sub ES {    my (\$n) = @_;    my @factors = factor \$n + 1;    my \$category = max map { defined \$cat{\$_} and \$cat{\$_} } @factors;    unless (defined \$cat{ \$factors[-1] }) {        \$category = max \$category, (1 + max map { \$cat{\$_} } factor 1 + \$factors[-1]);        \$cat{ \$factors[-1] } = \$category;    }    \$category} my %es;my \$upto = 200;push @{\$es{ES(\$_)}}, \$_ for @primes[1..\$upto];say "First \$upto primes, Erdös-Selfridge categorized:";say "\$_: " . join ' ', sort {\$a <=> \$b} @{\$es{\$_}} for sort keys %es; %es = ();\$upto = 1_000_000;say "\nSummary of first @{[comma \$upto]} primes, Erdös-Selfridge categorized:";push @{\$es{ES(\$_)}}, \$_ for @primes[1..\$upto];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;`
Output:
```First 200 primes, Erdös-Selfridge categorized:
1: 2 3 5 7 11 17 23 31 47 53 71 107 127 191 383 431 647 863 971 1151
2: 13 19 29 41 43 59 61 67 79 83 89 97 101 109 131 137 139 149 167 179 197 199 211 223 229 239 241 251 263 269 271 281 283 293 307 317 349 359 367 373 419 433 439 449 461 479 499 503 509 557 563 577 587 593 599 619 641 643 659 709 719 743 751 761 769 809 827 839 881 919 929 953 967 991 1019 1033 1049 1069 1087 1103 1187 1223
3: 37 103 113 151 157 163 173 181 193 227 233 257 277 311 331 337 347 353 379 389 397 401 409 421 457 463 467 487 491 521 523 541 547 569 571 601 607 613 631 653 683 701 727 733 773 787 797 811 821 829 853 857 859 877 883 911 937 947 983 997 1009 1013 1031 1039 1051 1061 1063 1091 1097 1117 1123 1153 1163 1171 1181 1193 1217
4: 73 313 443 617 661 673 677 691 739 757 823 887 907 941 977 1093 1109 1129 1201 1213
5: 1021

Summary of first 1,000,000 primes, Erdös-Selfridge categorized:
Category  1:  first:         2  last: 10,616,831  count: 46
Category  2:  first:        13  last: 15,482,669  count: 10,497
Category  3:  first:        37  last: 15,485,863  count: 201,987
Category  4:  first:        73  last: 15,485,849  count: 413,891
Category  5:  first:     1,021  last: 15,485,837  count: 263,109
Category  6:  first:     2,917  last: 15,485,857  count: 87,560
Category  7:  first:    15,013  last: 15,484,631  count: 19,389
Category  8:  first:    49,681  last: 15,485,621  count: 3,129
Category  9:  first:   532,801  last: 15,472,811  count: 363
Category 10:  first: 1,065,601  last: 15,472,321  count: 28
Category 11:  first: 8,524,807  last:  8,524,807  count: 1```

## Phix

Library: Phix/online

You can run this online here (but expect a blank screen for about 20s)

```with javascript_semantics
sequence escache = {}

function es_cat(integer p)
if p>length(escache) and platform()!=JS then
escache &= repeat(0,p-length(escache))
end if
integer category = escache[p]
if not category then
sequence f = filter(prime_factors(p+1,false,-1),">",3)
category = 1
if length(f) then
category += max(apply(f,es_cat))
end if
escache[p] = category
end if
return category
end function

procedure categorise(integer n)
sequence p = get_primes(n)
printf(1,"First %,d primes:\n",n)
atom t1 = time()
sequence es = {}
for i=1 to n do
if time()>t1 then
progress("categorising %d/%d...",{i,n})
t1 = time()+1
end if
integer category = es_cat(p[i])
while length(es)<category do
es = append(es,{})
end while
es[category] &= p[i]
end for
progress("")
for c=1 to length(es) do
sequence e = es[c]
if n=200 then
printf(1,"Category %d: %s\n",{c,join(shorten(e,"primes",5,"%d"),",")})
else
printf(1,"Category %2d: %7d .. %-8d  Count: %d\n",{c,e[1],e[\$],length(e)})
end if
end for
printf(1,"\n")
end procedure

atom t0 = time()
categorise(200)
categorise(1e6)
?elapsed(time()-t0)
```
Output:
```First 200 primes:
Category 1: 2,3,5,7,11,...,431,647,863,971,1151, (20 primes)
Category 2: 13,19,29,41,43,...,1069,1087,1103,1187,1223, (82 primes)
Category 3: 37,103,113,151,157,...,1163,1171,1181,1193,1217, (77 primes)
Category 4: 73,313,443,617,661,...,1093,1109,1129,1201,1213, (20 primes)
Category 5: 1021

First 1,000,000 primes:
Category  1:       2 .. 10616831  Count: 46
Category  2:      13 .. 15482669  Count: 10497
Category  3:      37 .. 15485863  Count: 201987
Category  4:      73 .. 15485849  Count: 413891
Category  5:    1021 .. 15485837  Count: 263109
Category  6:    2917 .. 15485857  Count: 87560
Category  7:   15013 .. 15484631  Count: 19389
Category  8:   49681 .. 15485621  Count: 3129
Category  9:  532801 .. 15472811  Count: 363
Category 10: 1065601 .. 15472321  Count: 28
Category 11: 8524807 .. 8524807   Count: 1

"11.0s"
```

Takes about twice as long under pwa/p2js.

## Raku

`use Prime::Factor;use Lingua::EN::Numbers;use Math::Primesieve;my \$sieve = Math::Primesieve.new; my %cat = 2 => 1, 3 => 1; sub Erdös-Selfridge (\$n) {    my @factors = prime-factors \$n + 1;    my \$category = max %cat{ @factors };    unless %cat{ @factors[*-1] } {        \$category max= ( 1 + max %cat{ prime-factors 1 + @factors[*-1] } );        %cat{ @factors[*-1] } = \$category;    }    \$category} my \$upto = 200; say "First { cardinal \$upto } primes; Erdös-Selfridge categorized:";.say for sort \$sieve.n-primes(\$upto).categorize: &Erdös-Selfridge; \$upto = 1_000_000; 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: &commafor \$sieve.n-primes(\$upto).categorize( &Erdös-Selfridge ).sort(+*.key)».value;`
Output:
```First two hundred primes; Erdös-Selfridge categorized:
1 => [2 3 5 7 11 17 23 31 47 53 71 107 127 191 383 431 647 863 971 1151]
2 => [13 19 29 41 43 59 61 67 79 83 89 97 101 109 131 137 139 149 167 179 197 199 211 223 229 239 241 251 263 269 271 281 283 293 307 317 349 359 367 373 419 433 439 449 461 479 499 503 509 557 563 577 587 593 599 619 641 643 659 709 719 743 751 761 769 809 827 839 881 919 929 953 967 991 1019 1033 1049 1069 1087 1103 1187 1223]
3 => [37 103 113 151 157 163 173 181 193 227 233 257 277 311 331 337 347 353 379 389 397 401 409 421 457 463 467 487 491 521 523 541 547 569 571 601 607 613 631 653 683 701 727 733 773 787 797 811 821 829 853 857 859 877 883 911 937 947 983 997 1009 1013 1031 1039 1051 1061 1063 1091 1097 1117 1123 1153 1163 1171 1181 1193 1217]
4 => [73 313 443 617 661 673 677 691 739 757 823 887 907 941 977 1093 1109 1129 1201 1213]
5 => [1021]

Summary of first one million primes; Erdös-Selfridge categorized:
Category  1: first:         2  last: 10,616,831  count: 46
Category  2: first:        13  last: 15,482,669  count: 10,497
Category  3: first:        37  last: 15,485,863  count: 201,987
Category  4: first:        73  last: 15,485,849  count: 413,891
Category  5: first:     1,021  last: 15,485,837  count: 263,109
Category  6: first:     2,917  last: 15,485,857  count: 87,560
Category  7: first:    15,013  last: 15,484,631  count: 19,389
Category  8: first:    49,681  last: 15,485,621  count: 3,129
Category  9: first:   532,801  last: 15,472,811  count: 363
Category 10: first: 1,065,601  last: 15,472,321  count: 28
Category 11: first: 8,524,807  last:  8,524,807  count: 1```

## Rust

`// [dependencies]// primal = "0.3" use std::collections::BTreeMap; struct ErdosSelfridge {    primes: Vec<usize>,    category: Vec<u32>,} impl ErdosSelfridge {    fn new(limit: usize) -> ErdosSelfridge {        let mut es = ErdosSelfridge {            primes: primal::Primes::all().take(limit).collect(),            category: Vec::new(),        };        es.category.resize(es.primes.len(), 0);        es    }     fn get_category(&mut self, index: usize) -> u32 {        if self.category[index] != 0 {            return self.category[index];        }        let mut max_category = 0;        let mut n = self.primes[index] + 1;        for i in 0.. {            let p = self.primes[i];            if p * p > n {                break;            }            let mut count = 0;            while n % p == 0 {                n /= p;                count += 1;            }            if count != 0 {                let category = if p <= 3 { 1 } else { 1 + self.get_category(i) };                max_category = std::cmp::max(max_category, category);            }        }        if n > 1 {            let i = self.get_index(n);            let category = if n <= 3 { 1 } else { 1 + self.get_category(i) };            max_category = std::cmp::max(max_category, category);        }        self.category[index] = max_category;        max_category    }     fn get_index(&self, prime: usize) -> usize {        self.primes.binary_search(&prime).unwrap()    }     fn get_primes_by_category(&mut self, limit: usize) -> BTreeMap<u32, Vec<usize>> {        let mut primes_by_category: BTreeMap<u32, Vec<usize>> = BTreeMap::new();        for i in 0..limit {            let category = self.get_category(i);            let prime = self.primes[i];            if let Some(primes) = primes_by_category.get_mut(&category) {                primes.push(prime);            } else {                let mut primes = Vec::new();                primes.push(prime);                primes_by_category.insert(category, primes);            }        }        primes_by_category    }} fn main() {    let mut es = ErdosSelfridge::new(1000000);    let primes_by_category = es.get_primes_by_category(200);    println!("First 200 primes:");    for (category, primes) in primes_by_category.iter() {        println!("Category {}:", category);        for i in 0..primes.len() {            print!(                "{:4}{}",                primes[i],                if (i + 1) % 15 == 0 { "\n" } else { " " }            );        }        print!("\n\n");    }    println!("First 1,000,000 primes:");    let primes_by_category = es.get_primes_by_category(1000000);    for (category, primes) in primes_by_category.iter() {        let first = primes[0];        let count = primes.len();        let last = primes[count - 1];        println!(            "Category {:2}: first = {:7}  last = {:8}  count = {}",            category, first, last, count        );    }}`
Output:
```First 200 primes:
Category 1:
2    3    5    7   11   17   23   31   47   53   71  107  127  191  383
431  647  863  971 1151

Category 2:
13   19   29   41   43   59   61   67   79   83   89   97  101  109  131
137  139  149  167  179  197  199  211  223  229  239  241  251  263  269
271  281  283  293  307  317  349  359  367  373  419  433  439  449  461
479  499  503  509  557  563  577  587  593  599  619  641  643  659  709
719  743  751  761  769  809  827  839  881  919  929  953  967  991 1019
1033 1049 1069 1087 1103 1187 1223

Category 3:
37  103  113  151  157  163  173  181  193  227  233  257  277  311  331
337  347  353  379  389  397  401  409  421  457  463  467  487  491  521
523  541  547  569  571  601  607  613  631  653  683  701  727  733  773
787  797  811  821  829  853  857  859  877  883  911  937  947  983  997
1009 1013 1031 1039 1051 1061 1063 1091 1097 1117 1123 1153 1163 1171 1181
1193 1217

Category 4:
73  313  443  617  661  673  677  691  739  757  823  887  907  941  977
1093 1109 1129 1201 1213

Category 5:
1021

First 1,000,000 primes:
Category  1: first =       2  last = 10616831  count = 46
Category  2: first =      13  last = 15482669  count = 10497
Category  3: first =      37  last = 15485863  count = 201987
Category  4: first =      73  last = 15485849  count = 413891
Category  5: first =    1021  last = 15485837  count = 263109
Category  6: first =    2917  last = 15485857  count = 87560
Category  7: first =   15013  last = 15484631  count = 19389
Category  8: first =   49681  last = 15485621  count = 3129
Category  9: first =  532801  last = 15472811  count = 363
Category 10: first = 1065601  last = 15472321  count = 28
Category 11: first = 8524807  last =  8524807  count = 1
```

## Wren

Library: Wren-math
Library: Wren-fmt

`import "./math" for Intimport "./fmt" for Fmt var limit = (1e6.log * 1e6 * 1.2).floor  // should be more than enoughvar primes = Int.primeSieve(limit) var prevCats = {} var cat // recursivecat = Fn.new { |p|    if (prevCats.containsKey(p)) return prevCats[p]    var pf = Int.primeFactors(p+1)    if (pf.all { |f| f == 2 || f == 3 }) return 1    if (p > 2) {        for (i in pf.count-1..1) {            if (pf[i-1] == pf[i]) pf.removeAt(i)        }    }     for (c in 2..11) {        if (pf.all { |f| cat.call(f) < c }) {            prevCats[p] = c            return c        }    }    return 12} var es = List.filled(12, null)for (i in 0..11) es[i] = [] System.print("First 200 primes:\n ")for (p in primes[0..199]) {    var c = cat.call(p)    es[c-1].add(p)}for (c in 1..6) {    if (es[c-1].count > 0) {        System.print("Category %(c):")        System.print(es[c-1])        System.print()    }} System.print("First million primes:\n")for (p in primes[200...1e6]) {    var c = cat.call(p)    es[c-1].add(p)}for (c in 1..12) {    var e = es[c-1]    if (e.count > 0) {        Fmt.print("Category \$-2d: First = \$7d  Last = \$8d  Count = \$6d", c, e[0], e[-1], e.count)    }}`
Output:
```First 200 primes:

Category 1:
[2, 3, 5, 7, 11, 17, 23, 31, 47, 53, 71, 107, 127, 191, 383, 431, 647, 863, 971, 1151]

Category 2:
[13, 19, 29, 41, 43, 59, 61, 67, 79, 83, 89, 97, 101, 109, 131, 137, 139, 149, 167, 179, 197, 199, 211, 223, 229, 239, 241, 251, 263, 269, 271, 281, 283, 293, 307, 317, 349, 359, 367, 373, 419, 433, 439, 449, 461, 479, 499, 503, 509, 557, 563, 577, 587, 593, 599, 619, 641, 643, 659, 709, 719, 743, 751, 761, 769, 809, 827, 839, 881, 919, 929, 953, 967, 991, 1019, 1033, 1049, 1069, 1087, 1103, 1187, 1223]

Category 3:
[37, 103, 113, 151, 157, 163, 173, 181, 193, 227, 233, 257, 277, 311, 331, 337, 347, 353, 379, 389, 397, 401, 409, 421, 457, 463, 467, 487, 491, 521, 523, 541, 547, 569, 571, 601, 607, 613, 631, 653, 683, 701, 727, 733, 773, 787, 797, 811, 821, 829, 853, 857, 859, 877, 883, 911, 937, 947, 983, 997, 1009, 1013, 1031, 1039, 1051, 1061, 1063, 1091, 1097, 1117, 1123, 1153, 1163, 1171, 1181, 1193, 1217]

Category 4:
[73, 313, 443, 617, 661, 673, 677, 691, 739, 757, 823, 887, 907, 941, 977, 1093, 1109, 1129, 1201, 1213]

Category 5:
[1021]

First million primes:

Category 1 : First =       2  Last = 10616831  Count =     46
Category 2 : First =      13  Last = 15482669  Count =  10497
Category 3 : First =      37  Last = 15485863  Count = 201987
Category 4 : First =      73  Last = 15485849  Count = 413891
Category 5 : First =    1021  Last = 15485837  Count = 263109
Category 6 : First =    2917  Last = 15485857  Count =  87560
Category 7 : First =   15013  Last = 15484631  Count =  19389
Category 8 : First =   49681  Last = 15485621  Count =   3129
Category 9 : First =  532801  Last = 15472811  Count =    363
Category 10: First = 1065601  Last = 15472321  Count =     28
Category 11: First = 8524807  Last =  8524807  Count =      1
```