Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
Check your math in your first example: 40 is not equal to 5*2*2*2*2. – GamrCorps Feb 22 at 17:39
    
@GamrCorps Ah, yes, thank you. – Cᴏɴᴏʀ O'Bʀɪᴇɴ Feb 22 at 17:40
    
How do you define the nth k-almost prime? What determines what order the k-almost primes are in? – GamrCorps Feb 22 at 17:51
3  
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].) – 2012rcampion Feb 22 at 18:45
1  
Why is a simple closed form banned? – CalculatorFeline Feb 23 at 5:14
up vote 8 down vote accepted

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!

share|improve this answer

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]
share|improve this answer

Julia, 84 78 59 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
share|improve this answer

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).
share|improve this answer
1  
I'm not aware of any encoding that can save these 9 characters as 9 bytes. – Oleh Prypin Feb 23 at 13:49
    
Jelly uses a custom encoding that represents the 256 character it understands with single bytes. – Dennis Feb 23 at 14:12

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.

share|improve this answer
    
This doesn't work for n=1. – IPoiler Feb 22 at 23:35
    
Also since PrimeOmega[1] evaluates to 0, &&#>1 is redundant. – IPoiler Feb 22 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.

share|improve this answer
    
2^(0+##), or just 2^## works. – CalculatorFeline Feb 23 at 5:21
    
@CatsAreFluffy Try 2^Sequence[1,2] to see why the latter fails. – IPoiler Feb 23 at 15:23

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
share|improve this answer

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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