A number is an   attractive number   if the number of its prime factors (whether distinct or not) is also prime.



Example

The number   20,   whose prime decomposition is   2 × 2 × 5,   is an   attractive number   because the number of its prime factors   (3)   is also prime.



Task

Show sequence items up to   120.



Reference

   The OEIS entry:   A063989: Numbers with a prime number of prime divisors.


/* Sieve of Eratosthenes */
proc nonrec sieve([*] bool prime) void:
    word p, c, max;
    max := (dim(prime,1)-1)>>1;
    prime[0] := false;
    prime[1] := false;
    for p from 2 upto max do prime[p] := true od;
    for p from 2 upto max>>1 do
        if prime[p] then
            for c from p*2 by p upto max do
                prime[c] := false
            od
        fi
    od
corp
 
/* Count the prime factors of a number */
proc nonrec n_factors(word n; [*] bool prime) word:
    word count, fac;
    fac := 2;
    count := 0;
    while fac <= n do
        if prime[fac] then
            while n % fac = 0 do
                count := count + 1;
                n := n / fac
            od
        fi;
        fac := fac + 1
    od;
    count
corp
 
/* Find attractive numbers <= 120 */
proc nonrec main() void:
    word MAX = 120;
    [MAX+1] bool prime;
    unsigned MAX i;
    byte col;
    sieve(prime);
    col := 0;
    for i from 2 upto MAX do
        if prime[n_factors(i, prime)] then
            write(i:4);
            col := col + 1;
            if col % 18 = 0 then writeln() fi
        fi
    od
corp