30
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Check your math in your first example: 40 is not equal to 5*2*2*2*2. \$\endgroup\$ – GamrCorps Feb 22 '16 at 17:39
  • \$\begingroup\$ @GamrCorps Ah, yes, thank you. \$\endgroup\$ – Conor O'Brien Feb 22 '16 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 Feb 22 '16 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\$ – 2012rcampion Feb 22 '16 at 18:45
  • 1
    \$\begingroup\$ Why is a simple closed form banned? \$\endgroup\$ – CalculatorFeline Feb 23 '16 at 5:14

12 Answers 12

8
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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]
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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

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
\$\endgroup\$
1
\$\begingroup\$

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.

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

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.

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

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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