30
1
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 52222. – GamrCorps – 2016-02-22T17:39:46.833
@GamrCorps Ah, yes, thank you. – Conor O'Brien – 2016-02-22T17:40:17.987
How do you define the nth k-almost prime? What determines what order the k-almost primes are in? – GamrCorps – 2016-02-22T17:51:58.727
@GamrCorps Similar to how you determine the nth prime: you can generate a list of the first n numbers with k prime factors, sorted from least to greatest, and take the last member in that list. – Conor O'Brien – 2016-02-22T17:55:54.287
3I don't think your expression for
f
in terms off[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 thatf[n,1] == 2*f[n,1]
.) – 2012rcampion – 2016-02-22T18:45:20.600@2012rcampion Oh, my mistake. It was a simple observation that was not founded by proof. – Conor O'Brien – 2016-02-22T19:11:56.820
1Why is a simple closed form banned? – CalculatorFeline – 2016-02-23T05:14:31.420
Your last paragraph doesn't make sense. There's no known closed form for the problem you are asking, and in fact there are proofs that such a closed form does not exists (when taking operations from certain sets of operations [e.g. surely no polynomial exists that produces all primes ]). – Bakuriu – 2016-02-23T11:13:41.733
@Bakuriu I don't know much about the proofs. I was merely trying to ban trivial solutions. – Conor O'Brien – 2016-02-23T12:09:51.067
What I'm saying is that there aren't trivial solutions. Just say that it must work with
1 <= n <= 100
and1 <= k <= 10
, so that storing the solutions in a table is infeasible and you are done. – Bakuriu – 2016-02-23T12:49:57.650