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.


class AttractiveNumber {
  function : Main(args : String[]) ~ Nil {    
    max := 120;
    "The attractive numbers up to and including {$max} are:"->PrintLine();
 
    count := 0;
    for(i := 1; i <= max; i += 1;) {
      n := CountPrimeFactors(i);
      if(IsPrime(n)) {
        " {$i}"->Print();
        if(++count % 20 = 0) {
          ""->PrintLine();
        };
      };
    };
 
    ""->PrintLine();     
  }
 
  function : IsPrime(n : Int) ~ Bool {
    if(n < 2) {
      return false;
    };
 
    if(n % 2 = 0) {
      return n = 2;
    };
 
    if(n % 3 = 0) {
      return n = 3;
    };
 
    d := 5;
    while(d *d <= n) {
      if(n % d = 0) {
        return false;
      };
      d += 2;
 
      if(n % d = 0) {
        return false;
      };
      d += 4;
    };
 
    return true;
  }
 
  function : CountPrimeFactors(n : Int) ~ Int {
    if(n = 1) { 
      return 0; 
    };
 
    if(IsPrime(n)) { 
      return 1; 
    };
 
    count := 0; 
    f := 2;
    while(true) {
      if(n % f = 0) {
        count++;
        n /= f;
        if(n = 1) { return count; };
        if(IsPrime(n)) { f := n; };
      }
      else if(f >= 3) { 
        f += 2; 
      }
      else {
        f := 3;
      };
    };
 
    return -1;    
  }
}