Almost prime

Almost prime is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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$.

Cf.

• Semiprime
• Category:Prime Numbers

C

<lang c>#include <stdio.h>

int kprime(int n, int k) { int p, f = 0; for (p = 2; f < k && p*p <= n; p++) while (0 == n % p) n /= p, f++;

return f + (n > 1) == k; }

int main(void) { int i, c, k;

for (k = 1; k <= 5; k++) { printf("k = %d:", k);

for (i = 2, c = 0; c < 10; i++) if (kprime(i, k)) { printf(" %d", i); c++; }

putchar('\n'); }

return 0; }</lang>

Output:

k = 1: 2 3 5 7 11 13 17 19 23 29
k = 2: 4 6 9 10 14 15 21 22 25 26
k = 3: 8 12 18 20 27 28 30 42 44 45
k = 4: 16 24 36 40 54 56 60 81 84 88
k = 5: 32 48 72 80 108 112 120 162 168 176

J

<lang J> (10 {. [:~.[:/:~[:,*/~)^:(i.5)~p:i.10

2  3  5  7  11  13  17  19  23  29
4  6  9 10  14  15  21  22  25  26
8 12 18 20  27  28  30  42  44  45

16 24 36 40 54 56 60 81 84 88 32 48 72 80 108 112 120 162 168 176</lang>

Explanation:

1. Generate 10 primes.
2. Multiply each of them by the first ten primes
3. Sort and find unique values, take the first ten of those
4. Multiply each of them by the first ten primes
5. Sort and find unique values, take the first ten of those

...

The results of the odd steps in this procedure are the desired result.

Perl 6

Recursive implementation. Quite slow. <lang perl6>sub is-k-almost-prime($n, $k) {

   $n != 1 and
   (state @)[$k][$n] //=
   $k == 1 ?? $n.is-prime !!
   is-k-almost-prime(

$n div (first $n %% *, grep &is-prime, 2 .. *), $k - 1

   );

}

for 1 .. 5 -> $k {

   say .[^10] given
   grep { is-k-almost-prime($_, $k) }, 2 .. *

}</lang>

Output:

2 3 5 7 11 13 17 19 23 29
4 6 9 10 14 15 21 22 25 26
8 12 18 20 27 28 30 42 44 45
16 24 36 40 54 56 60 81 84 88
32 48 72 80 108 112 120 162 168 176

Python

This imports Prime decomposition#Python

<lang python>from prime_decomposition import decompose from itertools import islice, count try:

   from functools import reduce

except:

   pass

def almostprime(n, k=2):

   d = decompose(n)
   try:
       terms = [d.next() for i in range(k)]
       return reduce(int.__mul__, terms, 1) == n
   except:
       return False

if __name__ == '__main__':

   for k in range(1,6):
       print('%i: %r' % (k, list(islice((n for n in count() if almostprime(n, k)), 10))))</lang>

Output:

1: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
2: [4, 6, 9, 10, 14, 15, 21, 22, 25, 26]
3: [8, 12, 18, 20, 27, 28, 30, 42, 44, 45]
4: [16, 24, 36, 40, 54, 56, 60, 81, 84, 88]
5: [32, 48, 72, 80, 108, 112, 120, 162, 168, 176]

REXX

<lang rexx>/*REXX program displays the N numbers of the first K k-almost primes*/ parse arg N K . /*get the arguments from the C.L.*/ if N== then N=10 /*No N? Then use the default.*/ if K== then K=5 /* " K? " " " " */

                                      /* [↓]  generate one line per  K.*/
    do i=1  for  K;   $=              /*generate  K   k-almost primes. */
    #=0                               /*number of k-almost primes found*/
        do j=1  until #==N            /*process an almost-prime N times*/
        if factr(j)\==i  then iterate /*not the correct k-almost prime?*/
        #=#+1                         /*bump the k-almost prime counter*/
        $=$ j                         /*append k-almost prime to list. */
        end   /*j*/                   /* [↑]   gen  N  k-almost primes.*/
    say N ' ' i"-almost primes:" $    /*display the k-almost primes.   */
    end       /*i*/                   /* [↑]  display a line for each K*/

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────FACTR subroutine────────────────────*/ factr: procedure; parse arg x 1 z; f=0 /*defines X and Z to the arg.*/ if x<2 then return 0 /*invalid number? Then return 0.*/

   do j=2  to 5;  if j\==4  then call .factr;  end    /*fast factoring.*/

j=5 /*start were we left off (J=5). */

   do y=0  by 2;  j=j+2 + y//4        /*insure it's not divisible by 3.*/
   if right(j,1)==5  then iterate     /*fast check  for divisible by 5.*/
   if j>z  then leave                 /*number reduced to a wee number?*/
   call .factr                        /*go add other factors to count. */
   end   /*y*/                        /* [↑]  find all factors in  X.  */

if f==0 then return 1 /*return 1 if the number is prime*/

             return f                 /*otherwise, return the # factors*/

/*──────────────────────────────────.FACTR subroutine───────────────────*/ .factr: do f=f+1 while z//j==0 /*keep dividing until it hurts. */

        z=z%j                         /*do an  (%)  integer divide.    */
        end   /*while*/               /* [↑]  whittle down the  Z  num.*/

f=f-1 /*adjust the factor count. */ return</lang> output when using the default input:

10   1-almost primes:  2 3 5 7 11 13 17 19 23 29
10   2-almost primes:  4 6 9 10 14 15 21 22 25 26
10   3-almost primes:  8 12 18 20 27 28 30 42 44 45
10   4-almost primes:  16 24 36 40 54 56 60 81 84 88
10   5-almost primes:  32 48 72 80 108 112 120 162 168 176