# That's a prime... almost

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


# Miscellaneous

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

• Check your math in your first example: 40 is not equal to 5*2*2*2*2. Feb 22, 2016 at 17:39
• @GamrCorps Ah, yes, thank you. Feb 22, 2016 at 17:40
• How do you define the nth k-almost prime? What determines what order the k-almost primes are in? Feb 22, 2016 at 17:51
• 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].) Feb 22, 2016 at 18:45
• Why is a simple closed form banned? Feb 23, 2016 at 5:14

## Pyth, 9 bytes

e.fqlPZQE


Explanation

          - 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

{~l~ḋ}ᶠ⁽t


# Explanation

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

ÆfL=³
ç#Ṫ


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

• I'm not aware of any encoding that can save these 9 characters as 9 bytes. Feb 23, 2016 at 13:49
• Jelly uses a custom encoding that represents the 256 character it understands with single bytes. Feb 23, 2016 at 14:12

## Pyke (commit 29), 8 bytes (noncompetitive)

.fPlQq)e


Explanation:

         - 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, 847859 57 bytes

f(n,k,i=1)=n>0?f(n-(sum(values(factor(i)))==k),k,i+1):i-1


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.

Ungolfed:

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)
else
# Otherwise we return i-1 (i will have been incremented one too
# many times, hence the -1)
return i - 1
end
end


# Vyxal, 8 bytes

λǐL⁰=;ȯt


Try it Online!

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


# Brachylog, 18 bytes

,1{hH&t<NḋlH;N}ⁱ⁽t


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


# Mathematica, 56 51 bytes

Last@Select[Range[2^##],PrimeOmega@#==n&/.n->#2,#]&


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

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

# Mathematica, 53 49 Bytes

Cases[Range[2^(#2+#)],x_/;PrimeOmega@x==#2][[#]]&


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.

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

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

:YqiZ^!XpSu1G)


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):
z=1;c=0
while c<n:z+=1;c+=(sum(sympy.factorint(z).values())==k)
return z


Ungolfed:

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!