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.

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)
