Eso es primo ... casi

30

Si alguna vez aprendió sobre números primos en la clase de matemáticas, probablemente haya tenido que, en un momento, determinar si un número es primo. Probablemente te hayas equivocado mientras todavía los estabas aprendiendo, por ejemplo, confundiendo 39 con un primo. Bueno, no se preocupe, ya que 39 es un semiprime, es decir, que es el producto de dos números primos.

Del mismo modo, podemos definir un k- primo casi como el producto de k números primos. Por ejemplo, 40 es el 4to 4-casi primo; 40 = 5 * 2 * 2 * 2, el producto de 4 factores.

Su tarea es escribir un programa / función que acepta dos enteros n y k como entrada y de salida / retorno del n º k -casi número primo. Este es un código de golf, por lo que gana el programa más corto en bytes.

Casos de prueba

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

Diverso

Debe generar los primos usted mismo por cualquier medio que no sea una forma cerrada simple, si existe una forma cerrada.

Conor O'Brien
fuente
Comprueba tus matemáticas en tu primer ejemplo: 40 no es igual a 5 * 2 * 2 * 2 * 2.
GamrCorps
@GamrCorps Ah, sí, gracias.
Conor O'Brien
¿Cómo define el enésimo k-casi primo? ¿Qué determina en qué orden están los primos k-casi?
GamrCorps
3
No creo que su expresión fen términos de f[n,1]sea ​​correcta, ya que las listas de casi primos contienen números impares (por ejemplo, los dos últimos ejemplos, que no se pueden expresar como el producto de una potencia de dos y un primo). (Y también dice eso f[n,1] == 2*f[n,1].)
2012 Arcampion
1
¿Por qué está prohibida una forma cerrada simple?
CalculatorFeline

Respuestas:

5

Brachylog , 9 bytes

Vencer a @sundar usando la mitad de bytes

{~l~ḋ}ᶠ⁽t

Explicación

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

Pruébalo en línea!

Kroppeb
fuente
4

Pyke (commit 29), 8 bytes (no competitivo)

.fPlQq)e

Explicación:

         - 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]
Azul
fuente
4

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

Esta es una función recursiva que acepta dos enteros y devuelve un entero. El enfoque aquí es verificar la suma de los exponentes en la factorización prima contra k.

Sin golf:

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
Alex A.
fuente
4

Jalea, 9 bytes

ÆfL=³
ç#Ṫ

Pruébalo en línea!

Cómo funciona

Ç#Ṫ    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).
Dennis
fuente
1
No conozco ninguna codificación que pueda guardar estos 9 caracteres como 9 bytes.
Oleh Prypin
1
Jelly usa una codificación personalizada que representa los 256 caracteres que entiende con bytes individuales.
Dennis
3

Brachylog , 18 bytes

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

Pruébalo en línea!

                      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
sundar - Restablece a Monica
fuente
1

Mathematica, 56 51 bytes

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

Advertencia: esto es teórico. No ejecute valores> 4. Reemplace 2 ^ ## con una expresión más eficiente.

CalculadoraFeline
fuente
Esto no funciona para n=1.
IPoiler
Además, dado que se PrimeOmega[1]evalúa como 0, &&#>1es redundante.
IPoiler
1

Mathematica, 53 49 bytes

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

Genera una lista de enteros basada en un límite superior suelto. PrimeOmegalos recuentos de los factores primos con multiplicidades, la k -casi prime Casesse toman de la lista, y la n se devuelve º miembro de ese subconjunto.

IPoiler
fuente
2 ^ (0 + ##), o solo 2 ^ ## funciona.
CalculatorFeline
@CatsAreFluffy Intenta 2^Sequence[1,2]ver por qué falla este último.
IPoiler
1

Haskell, 88 bytes

Probablemente se pueda jugar mucho más al golf, ya que todavía soy un novato en Haskell. La función qdevuelve el número de factores de su argumento, y lo fusa para obtener el nthelemento de una lista hecha de todos los números que tienen kfactores.

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
falla
fuente
1

MATL, 14 bytes

:YqiZ^!XpSu1G)

Pruébalo en 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
sundar - Restablece a Monica
fuente
0

Python 3, 100 bytes

Esta es una función de fuerza bruta muy simple. Comprueba cada número a partir de 2 con sympyla factorintfunción de 's hasta que ha encontrado n kcasi primos, en cuyo punto, la función devuelve el nth de estos.

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

Sin golf:

Lo uso sum(factorint(a).values())porque factorintdevuelve un diccionario de factor: exponentpares. Tomar los valores del diccionario (los exponentes) y sumarlos me dice cuántos factores primos hay y, por lo tanto, cuál es keste kprimo casi.

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