/* 

  Almost prime in Picat.

  http://rosettacode.org/wiki/Almost_prime
  """
  A k-Almost-prime is a natural number n that is the product of k 
  (possibly identical) primes. So, for example, 1-almost-primes, 
  where k = 1, are the prime numbers themselves; 2-almost-primes 
  are the semiprimes.

  The task is to write a function/method/subroutine/... that generates 
  k-almost primes and use it to create a table here of the first ten 
  members of k-Almost primes for 1 < = K < = 5. 
  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


import util.
% import cp.


main => go.

% Much faster and correct!
% {{trans|J}}
go =>
  N = 10,
  Ps = primes(100).take(N),
  println(1=Ps),
  T = Ps,
  foreach(K in 2..5)
    T := mul_take(Ps,T,N),
    println(K=T)
  end,
  nl,
  foreach(K in 6..25)
    T := mul_take(Ps,T,N),    
    println(K=T)
  end,
  nl.

take(L,N) = [L[I] : I in 1..N].

% take first N values of L1 x L2 
mul_take(L1,L2,N) = [I*J : I in L1, J in L2, I<=J].sort_remove_dups().take(N).



% THIS IS NOT CORRECT. Why??
% go2/0 is correct
go_bad =>

  foreach(K in 1..5)
    println(K=almost_prime(K,10))
  end,
  nl,
  
  foreach(K in 6..15)
    println(K=almost_prime(K,10))
  end,

  

  nl.

%
% Return N K-almost primes
%
almost_prime(K,N) = AlmostPrimes =>
  AlmostPrimes = [],
  C = 0,
  I = 2,
  while (C < N)
    if num_prime_factors(I) == K then
      AlmostPrimes := AlmostPrimes ++ [I],
      C := C + 1
    end,
    I := I + 1
  end.

% Number of prime factors of number N
num_prime_factors(N) = NF =>
  NF = 0,
  M = N,
  while (M mod 2 == 0) 
      NF := NF + 1,
      M := M div 2 
  end,
  T = 3,
  while (M > 1, T < ceiling(sqrt(M)))
     while (M mod T == 0) 
       NF := NF + 1,
       M := M div T
     end,
     T := T + 2 
  end,
  if M > 1 then
     NF := NF + 1
  end.