If you've ever learned about primes in math class, you've probably have had to, at one point, determine if a number is prime. You've probably messed up while you were still learning them, for example, mistaking 39 for a prime. Well, not to worry, as 39 is a semiprime, i.e., that it is the product of two primes.

Similarly, we can define a k-almost prime as being the product of k prime numbers. For example, 40 is the 4th 4-almost prime; 40 = 5*2*2*2, the product of 4 factors.

Your task is to write a program/function that accepts two integers n and k as input and output/return the nth k-almost prime number. This is a code-golf, so the shortest program in bytes wins.

Test cases

n, k => output
n, 1 => the nth prime number
1, 1 => 2
3, 1 => 5
1, 2 => 4
3, 2 => 9
5, 3 => 27


You have to generate the primes yourself by any means other than a simple closed form, if such a closed form exists.

  • \$\begingroup\$ Check your math in your first example: 40 is not equal to 5*2*2*2*2. \$\endgroup\$
    – GamrCorps
    Commented Feb 22, 2016 at 17:39
  • \$\begingroup\$ @GamrCorps Ah, yes, thank you. \$\endgroup\$ Commented Feb 22, 2016 at 17:40
  • \$\begingroup\$ How do you define the nth k-almost prime? What determines what order the k-almost primes are in? \$\endgroup\$
    – GamrCorps
    Commented Feb 22, 2016 at 17:51
  • 3
    \$\begingroup\$ I don't think your expression for f in terms of f[n,1] is correct, since the lists of almost-primes contain odd numbers (e.g. the last two examples, which are not expressible as the product of a power of two and a prime). (And it also says that f[n,1] == 2*f[n,1].) \$\endgroup\$ Commented Feb 22, 2016 at 18:45
  • 1
    \$\begingroup\$ Why is a simple closed form banned? \$\endgroup\$ Commented Feb 23, 2016 at 5:14

14 Answers 14


Pyth, 9 bytes



          - autoassign Q = eval(input())
     PZ   -      prime_factors(Z) 
    l     -     len(^)
   q   Q  -    ^ == Q
 .f     E -  first eval(input()) of (^ for Z in range(inf))
e         - ^[-1]

Try it here!

Or try a test suite!


Brachylog, 9 bytes

Beating @sundar by using half as much bytes



                    --  Input like [n,k]
{    }ᶠ⁽            --      Find the first n values which
   ~ḋ               --          have a prime decomposition
 ~l                 --          of length k
        t           --      and take the last one

Try it online!


Jelly, 9 bytes


Try it online!

How it works

Ç#Ṫ    Main link. Left input: k. Right input: n.

Ç      Apply the helper link to k, k + 1, k + 2, ... until...
 #       n matches are found.
  Ṫ    Retrieve the last match.

ÆfL=³  Helper link. Left argument: k (iterator)

Æf     Yield the prime factors of k.
  L    Compute the length of the list, i.e., the number of prime factors.
   =³  Compare the result with k (left input).
  • 1
    \$\begingroup\$ I'm not aware of any encoding that can save these 9 characters as 9 bytes. \$\endgroup\$ Commented Feb 23, 2016 at 13:49
  • 1
    \$\begingroup\$ Jelly uses a custom encoding that represents the 256 character it understands with single bytes. \$\endgroup\$
    – Dennis
    Commented Feb 23, 2016 at 14:12

Pyke (commit 29), 8 bytes (noncompetitive)



         - autoassign Q = eval_or_not(input())
.f    )  - First eval_or_not(input) of (^ for i in range(inf))
  P      -    prime_factors(i)
   l     -   len(^)
     q   -  ^==V
    Q    -   Q
       e - ^[-1]

Julia, 84 78 59 57 bytes


This is a recursive function that accepts two integers and returns an integer. The approach here is to check the sum of the exponents in the prime factorization against k.


function f(n, k, i=1)
    # We initialize a counter i as a function argument.

    # Recurse while we've encountered fewer than n k-almost primes
    if n > 0
        # If the sum of the exponents in the prime factorization of i is
        # equal to k, there are k prime factors of i. We subtract a boolean
        # from n, which is implicitly cast to an integer, which will
        # decrement n if i is k-almost prime and leave it as is otherwise.
        return f(n - (sum(values(factor(i))) == k), k, i + 1)
        # Otherwise we return i-1 (i will have been incremented one too
        # many times, hence the -1)
        return i - 1

Vyxal, 8 bytes


Try it Online!

λ    ;ȯt # Nth number where
 ǐL      # Prime factor length
   ⁰=    # Equal to input

Brachylog, 18 bytes


Try it online!

                      Implicit input, say [5, 3]
,1                    Append 1 to the input list. [5, 3, 1]
  {           }ⁱ⁽     Repeat this predicate the number of times given by
                        the first element of the list (5),
                        on the rest of the list [3, 1]
   hH&                Let's call the first element H
      t<N             There is a number N greater than the second element
         ḋ            Whose prime factorization's
          l           length
           H          is equal to H
            ;N        Then, pair that N with H and let that be input for
                      the next iteration
                 t    At the end of iterations, take the last N
                      This is implicitly the output

Sidef, 21 bytes


Mathematica, 56 51 bytes


Warning: This is theoretical. Do not run for any values>4. Replace 2^## with a more efficient expression.

  • \$\begingroup\$ This doesn't work for n=1. \$\endgroup\$
    – IPoiler
    Commented Feb 22, 2016 at 23:35
  • \$\begingroup\$ Also since PrimeOmega[1] evaluates to 0, &&#>1 is redundant. \$\endgroup\$
    – IPoiler
    Commented Feb 22, 2016 at 23:41

Mathematica, 53 49 Bytes


Generates a list of integers based on a loose upper bound. PrimeOmega counts the prime factors with multiplicities, the k-almost prime Cases are taken from the list, and the nth member of that subset is returned.

  • \$\begingroup\$ 2^(0+##), or just 2^## works. \$\endgroup\$ Commented Feb 23, 2016 at 5:21
  • \$\begingroup\$ @CatsAreFluffy Try 2^Sequence[1,2] to see why the latter fails. \$\endgroup\$
    – IPoiler
    Commented Feb 23, 2016 at 15:23

Haskell, 88 bytes

Can probably be golfed a lot more, as I'm still a newbie to Haskell. The function q returns the number of factors of its argument, and f uses that to get take the nth element of a list made from all numbers that have k factors.

q n|n<2=0|1>0=1+q(div n ([x|x<-[2..],mod n x<1]!!0))
f n k=filter(\m->q m==k)[1..]!!n-1

MATL, 14 bytes


Try it on MATL Online

:               % Take first input n implicitly, make range 1 to n
 Yq             % Get corresponding prime numbers (1st prime to nth prime)
   i            % Take the second input k
    Z^          % Take the k-th cartesian power of the primes list 
                % (Getting all combinations of k primes)
      !Xp       % Multiply each combination (2*2*2, 2*2*3, 2*2*5, ...)
         Su     % Sort and unique
           1G)  % Take the n-th element of the result

Python 3, 100 bytes

This is a very simple brute force function. It checks every number starting from 2 with sympy's factorint function until it has found n k-almost primes, at which point, the function returns the nth of these.

import sympy
def a(n,k):
 while c<n:z+=1;c+=(sum(sympy.factorint(z).values())==k)
 return z


I use sum(factorint(a).values()) because factorint returns a dictionary of factor: exponent pairs. Grabbing the values of the dictionary (the exponents) and summing them tells me how many prime factors there are and thus what k this k-almost prime is.

from sympy import factorint
def almost(n, k):
    z = 1
    count = 0
    while count < n: 
        z += 1
        if sum(factorint(a).values()) == k:
            count += 1
    return z

Python 2, 76 bytes

f=lambda n,k,p=2,c=0:c==k if p>n else f(n,k,p+1,c)if n%p else f(n/p,k,p,c+1)

Try it online!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.