Rosetta Code

Erdös-Selfridge categorization of primes

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.

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

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., 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 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 io
kernel math math.primes math.primes.factors math.statistics
prettyprint 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... nl
1,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 enough
var 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.

J

Implementation: 

pcat=: {{ assert. 1 p: y
  1+>./0,pcat(q:1+y)-.2 3
}}M."0

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

To find the prime category of a prime, we find the prime factorization of the next larger integer, and find the category of each of those factors other than 2 or 3. The prime's category is one greater than the maximum of these factor categories (with an explicit 0 for the maximum when there are factors greater than 3)

First 200 primes -- category is in left box, primes are in right box: 

   (,.~<@#\) (</.~ 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                                                                                                                                                                                                                                                                  │
├─┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│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                                                                                                                                                                                                                                                                                                                               │
└─┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

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: 

   (,.~#\) (({.,{:,#)/.~ pcat) p:i.1e6
 1       2 10616831     46
 2      13 15482669  10497
 3      37 15485863 201987
 4      73 15485849 413891
 5    1021 15485837 263109
 6    2917 15485857  87560
 7   15013 15484631  19389
 8   49681 15485621   3129
 9  532801 15472811    363
10 1065601 15472321     28
11 8524807  8524807      1

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 category
end

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)
    end
end

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

Mathematica /Wolfram Language

Imperative implementation

ClearAll[SpecialPrimeFactors]
SpecialPrimeFactors[p_Integer] := FactorInteger[p + 1][[All, 1]]

ps = Prime[Range[200]];
cs = {{2, 3}};
Do[
  If[Length[ps] > 0,
   newc = 
    Select[ps, 
     Complement[SpecialPrimeFactors[#], Catenate[cs]] === {} &];
   AppendTo[cs, newc];
   ps = Complement[ps, newc];
   ,
   Break[]
   ]
  ,
  {n, 1, \[Infinity]}
  ];
Do[
 Print["Category: ", i - 1];
 Print@Multicolumn[cs[[i]], {Automatic, 10}]
 ,
 {i, Length[cs]}
 ]


ps = Prime[Range[1000000]];
ps = Parallelize[{#, SpecialPrimeFactors[#]} & /@ ps];
cs = {{2, 3}};
Do[
  If[Length[ps] > 0,
   newcs = Last[cs];
   ps[[All, 2]] = ps[[All, 2]] /. Dispatch[Thread[newcs -> Nothing]];
   newc = Select[ps, Last/*Length/*EqualTo[0]];
   ps = Complement[ps, newc];
   newc = newc[[All, 1]];
   AppendTo[cs, newc];
   ,
   Break[]
   ]
  ,
  {n, 1, \[Infinity]}
  ];

TableForm[{First[#], Last[#], Length[#]} & /@ Rest[cs], 
 TableHeadings -> {Automatic, {"First", "Last", "Count"}}, 
 TableAlignments -> Right]
Output:
Category: 0
2	3

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

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

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

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

Category: 5
1021

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

Functional implementation

ClearAll[ErdosSelfridgeCategory, CategorySizesTable, categories];

ErdosSelfridgeCategory[n_] := ErdosSelfridgeCategory[n] =
   If[ Last[primesToCheck = FactorInteger[n + 1][[All, 1]]] <= 3,
    1,
    1 + Max[ErdosSelfridgeCategory /@ primesToCheck]
    ];

(* Display the first 200 primes allocated to their category *)

categories = GatherBy[Prime[Range[200]], ErdosSelfridgeCategory];

Print["First 200 primes by Erdös-Selfridge category:\n"]

Do[
    Print["Class ", i, ":"];
    Print[
        TableForm[
            Partition[
                Map[StringPadLeft[ToString[#], 5] &, categories[[i]]], UpTo[12]],
        TableAlignments -> Right]
    ],
    {i, Length[categories]}
];

(* Show the number of primes in each category for the first million primes *)

Print["Calculating Erdős-Selfridge categories for the first million primes...."]

{seconds, categories} = 
  AbsoluteTiming[GatherBy[Prime[Range[10^6]], ErdosSelfridgeCategory]];

Print["Calculation took ", seconds " seconds."];

CategorySizesTable[categories_List] :=
  TableForm[
   Table[{Min[categories[[n]]], Max[categories[[n]]], 
     Length[categories[[n]]]}, {n, Length[categories]}], 
   TableHeadings -> {Automatic, {"First", "Last", "Count"}}, 
   TableAlignments -> Right];

Print[CategorySizesTable[categories]]
Output:
First 200 primes by Erdös-Selfridge category:

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

Class 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		

Class 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							

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

Class 5:
 1021

Calculating Erdős-Selfridge categories for the first million primes....
Calculation took 10.2376  seconds.

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

Nim

Translation of: Wren

Translation of Wren program with some modifications. As we don’t use a library to find the prime factors, we defined our own function to return the list without duplicates. The program runs in about 2.5 seconds. 

import std/[bitops, math, sequtils, strformat, strutils, tables]

type Sieve = object
  data: seq[byte]

func `[]`(sieve: Sieve; idx: Positive): bool =
  ## Return value of element at index "idx".
  let idx = idx shr 1
  let iByte = idx shr 3
  let iBit = idx and 7
  result = sieve.data[iByte].testBit(iBit)

func `[]=`(sieve: var Sieve; idx: Positive; val: bool) =
  ## Set value of element at index "idx".
  let idx = idx shr 1
  let iByte = idx shr 3
  let iBit = idx and 7
  if val: sieve.data[iByte].setBit(iBit)
  else: sieve.data[iByte].clearBit(iBit)

func newSieve(lim: Positive): Sieve =
  ## Create a sieve with given maximal index.
  result.data = newSeq[byte]((lim + 16) shr 4)

func initPrimes(lim: Positive): seq[Natural] =
  ## Initialize the list of primes from 2 to "lim".
  var composite = newSieve(lim)
  composite[1] = true
  for n in countup(3, sqrt(lim.toFloat).int, 2):
    if not composite[n]:
      for k in countup(n * n, lim, 2 * n):
        composite[k] = true
  result.add 2
  for n in countup(3, lim, 2):
    if not composite[n]:
      result.add n

const Limit = int(ln(1e6) * 1e6 * 1.2)
let primes = initPrimes(Limit)

func primeFactors(n: Positive): seq[Positive] =
  ## Return the list of prime factors of "n".
  ## Duplicate primes are excluded.
  var n = n
  var last = 0
  while (n and 1) == 0:
    if last != 2:
      result.add 2
      last = 2
    n = n shr 1
  var d = 3
  while d * d <= n:
    while n mod d == 0:
      if last != d:
        result.add d
        last = d
      n = n div d
    inc d, 2
  if n > 1: result.add n

type Category = 1..12
var prevCats: Table[int, int]

proc cat(p: Natural): Category =
  ## Recursive procedure to compute the catagory of "p".
  if p in prevCats: return prevCats[p]
  let pf = primeFactors(p + 1)
  if pf.allIt(it == 2 or it == 3):
    return 1
  for c in 2..11:
    if pf.allIt(cat(it) < c):
      prevCats[p] = c
      return c
  result = 12


var es: array[Category, seq[Positive]]

echo "First 200 primes:\n"
for p in primes[0..199]:
  es[p.cat].add p
for c in 1..6:
  if es[c].len > 0:
    echo &"Category {c}:"
    echo es[c].join(" ")
    echo()

echo "First million primes:\n"
for p in primes[200..999_999]:
  es[p.cat].add p
for c in 1..12:
  let e = es[c]
  if e.len > 0:
    echo &"Category {c:>2}: first = {e[0]:>7}  last = {e[^1]:>8}  count = {e.len:>6}"
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

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: &comma
for $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

RPL

Works with: RPL version HP49-C
« 5 { { 2 3 } } 0 → catg f
  « 1 ROT START 
       DUP 1 + FACTORS 0. 
       1 PICK3 SIZE FOR j 
          OVER j GET
          IF DUP 3 ≤ THEN NOT
          ELSE 
             'f' STO 
             catg 1. « f POS » DOLIST 0. > 1. POS 
          END 
          MAX 
       2 STEP 
       NIP 1 +
      IF DUP catg SIZE ≤
      THEN catg SWAP DUP2 GET 4 PICK + PUT 'catg' STO
      ELSE DROP 'catg' OVER 1. →LIST 1. →LIST STO+ END 
      NEXTPRIME
   NEXT 
   DROP catg
» » '→ESCLASS' STO  

200 →ESCLASS'
Output:
1: { { 2 3 5 7 11 17 23 31 47 53 71 107 127 191 383 431 647 863 971 1151 } { 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 1231 } { 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 1229 } { 73 313 443 617 661 673 677 691 739 757 823 887 907 941 977 1093 1109 1129 1201 1213 } { 1021 } }

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

Sidef 

func Erdös_Selfridge_class(n, s=1) is cached {
    var f = factor_exp(n+s)
    f.last.head > 3 || return 1
    f.map {|p| __FUNC__(p.head, s) }.max + 1
}

say "First two hundred primes; Erdös-Selfridge categorized:"
200.pn_primes.group_by(Erdös_Selfridge_class).sort_by{.to_i}.each_2d {|k,v|
    say "#{k} => #{v}"
}

say "\nSummary of first 10^6 primes; Erdös-Selfridge categorized:";
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)
}
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 10^6 primes; Erdös-Selfridge categorized:
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

Runs in about 23.5 seconds. 

import "./math" for Int
import "./fmt" for Fmt

var limit = (1e6.log * 1e6 * 1.2).floor  // should be more than enough
var primes = Int.primeSieve(limit)

var prevCats = {}

var cat // recursive
cat = 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
Retrieved from "https://rosettacode.org/wiki/Erdös-Selfridge_categorization_of_primes?oldid=363330"