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

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