Una forma de representar un número natural es multiplicando exponentes de números primos. Por ejemplo, 6 puede representarse con 2 ^ 1 * 3 ^ 1, y 50 puede representarse con 2 ^ 1 * 5 ^ 2 (donde ^ indica exponencia). El número de números primos en esta representación puede ayudar a determinar si es más corto usar este método de representación, en comparación con otros métodos. Pero debido a que no quiero calcularlos a mano, necesito un programa que lo haga por mí. Sin embargo, como tendré que recordar el programa hasta que llegue a casa, debe ser lo más breve posible.

Tu tarea:

Escriba un programa o función para determinar cuántos primos distintos hay en esta representación de un número.

Entrada:

Un número entero n tal que 1 <n <10 ^ 12, tomado por cualquier método normal.

Salida:

El número de primos distintos que se requieren para representar la entrada, como se describe en la introducción.

Casos de prueba:

24      -> 2 (2^3*3^1)
126     -> 3 (2^1*3^2*7^1)
1538493 -> 4 (3^1*11^1*23^1*2027^1)
123456  -> 3 (2^6*3^1*643^1)

Este es OEIS A001221 .

Puntuación:

Este es el código de golf , ¡la puntuación más baja en bytes gana!

MATL , 4 3 bytes

-1 byte gracias a Luis Mendo

YFz

Pruébalo en línea!

YF         Exponents of prime factors
  z        Number of nonzeros

Respuesta original:

Yfun

Pruébalo en línea!

Una muy buena Yfunrespuesta.

          (Implicit input)
Yf         Prime factorization
  u        Unique
   n       Numel
           (Implicit output)

05AB1E , 2 bytes

^{otra respuesta bastante aburrida ...}

fg

Un programa completo que acepta una entrada numérica e imprime el resultado.

Pruébalo en línea!

¿Cómo?

fg - implicitly take input
f  - get the prime factors with no duplicates
 g - get the length
   - implicit print

Mathematica, 7 bytes

PrimeNu

Sí, hay un incorporado.

Mathematica, 21 bytes

Length@*FactorInteger

El largo camino alrededor.

Gaia , 2 bytes

^{Otra respuesta bastante aburrida ... --- J. Allan}

ḋl

Pruébalo en línea!

• ḋ- Factorización prima como pares [primo, exponente] .

• l - Longitud.

Python 2, 56 bytes

f=lambda n,p=2,k=1:n/p and[f(n,p+1),k+f(n/p,p,0)][n%p<1]

Retina , 31 30 bytes

&`(?!(11+)\1+$)(11+)$(?<=^\2+)

La entrada está en unario.

¡Gracias a @MartinEnder por jugar al golf de 1 byte!

Pruébalo en línea! (incluye convertidor decimal a unario)

Cómo funciona

Dado que el programa consiste en una expresión regular única con el &modificador, Retina simplemente cuenta la cantidad de coincidencias superpuestas . Se supone que la entrada consiste en n repeticiones de 1 y nada más.

La anticipación negativa

(?!(11+)\1+$)

coincide en ubicaciones entre 1 's que no son seguidas por dos o más 1 ' s ( 11+), seguidas de una o más repeticiones de la misma cantidad de 1 's ( \1+), seguidas por el final de input ( $).

Cualquier número compuesto ab con a, b> 1 puede escribirse como b repeticiones de una repetición de 1 , por lo que la búsqueda anticipada solo coincide con las ubicaciones seguidas de p repeticiones de 1 , donde p = 1 o p es primo.

La expresión regular

(11+)$

se asegura de que p> 1 requiera al menos dos 1 's ( 11+) y almacena la cola de 1 ' s en el segundo grupo de captura ( \2).

Finalmente, la mirada positiva detrás

(?<=^\2+)

verifica que toda la entrada consiste en kp ocurrencias ( k ≥ 1 ) de 1 , verificando que p divide la entrada.

Por lo tanto, cada coincidencia corresponde a un único divisor primo p .

Bash + GNU utilidades, 33

• 1 byte guardado gracias a @Dennis

factor|grep -Po ' \d+'|uniq|wc -l

Pruébalo en línea .

Explicación

factor|                            # Split input into prime factors
       grep -Po ' \d+'|            # group factors onto lines
                       uniq|       # remove duplicates
                            wc -l  # count the lines

Jalea , 3 bytes

^{una respuesta bastante aburrida ...}

ÆFL

Un enlace monádico que toma un número y devuelve un número

Pruébalo en línea!

¿Cómo?

ÆFL - Link: number, n
ÆF  - prime factorisation as a list of prime, exponent pairs
  L - length

Ohm v2 , 2 bytes

ml

Pruébalo en línea!

Los dos elementos integrados están uno al lado del otro en la documentación jajaja.

Jalea , 2 bytes

^{Otra respuesta bastante aburrida ... --- J. Allan}

Æv

Pruébalo en línea!

Un incorporado.

Alice , 10 bytes

/o
\i@/Dcd

Pruébalo en línea!

Explicación

/o
\i@/...

Este es solo el marco estándar para programas aritméticos pesados ​​lineales que necesitan E / S decimal. El programa en sí mismo es simplemente:

Dcd

Que hace:

D    Deduplicate prime factors. Does what it sounds like: for every p^k which
     is a divisor n, this divides n by p^(k-1).
c    Push the individual prime factors of n. Since we've deduplicated them
     first, the number of factors is equal to the value we're looking for.
d    Push the stack depth, i.e. the number of unique prime factors.

JavaScript 45 bytes

* Para @SEJPM solicite una explicación: lo que estoy haciendo aquí es esto: voy de 2 - n (que cambia, y eventualmente será el factor primo más grande) - ahora si el número actual se divide ni quiero contarlo solo una vez (incluso aunque puede ser un factor de 2 * 2 * 2 * 3 - 2 se cuenta una vez), por lo que la "j" aparece en la imagen, cuando j no se especifica en la llamada de la función - j recibirá el valor de " undefined ", y cuando n% i == 0 llamo a la función con j = 1 en la siguiente llamada) - y luego solo agrego 1 cuando j es igual a undefined, que es! j + Función (n / i, i, ( j = 1 o solo 1)). No cambio i en este asunto porque aún puede ser divisible por i nuevamente (2 * 2 * 3) pero luego j será igual a 1 y no contará como factor. Espero haberlo explicado lo suficientemente bien.

P=(n,i=2,j)=>i>n?0:n%i?P(n,i+1):!j+P(n/i,i,1)

console.log(P(1538493)==4);
console.log(P(24)==2);
console.log(P(126)==3);
console.log(P(123456)==3);

si el último primo es muy grande, tendrá una pila máxima de llamadas; si es un problema, puedo hacer uno iterativo

CJam , 7 5 bytes

¡Gracias a Martin Ender por 2 bytes de descuento!

{mF,}

Bloque anónimo (función) que espera el número de entrada en la pila y lo reemplaza por el número de salida.

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

{   }   e# Define block
 mF     e# List of (prime, exponent) pairs
   ,    e# Length

Brachylog , 3 bytes

ḋdl

Pruébalo en línea!

Explicación

ḋ      Prime decomposition
 d     Remove duplicates
  l    Length

Pyth, 3 bytes

l{P

Banco de pruebas

Longitud ( l) del conjunto ( {) de factores primos ( P) de la entrada.

Casco , 3 bytes

Lup

Pruébalo en línea!

Explicación

  p  -- prime factors
 u   -- unique elements
L    -- length

En realidad , 2 bytes

^{Otra respuesta bastante aburrida ... --- J. Allan}

yl

Pruébalo en línea!

El primer personaje puede ser reemplazado por w.

Pyke , 3 bytes

P}l

Pruébalo aquí!

Python 3 , 68 67 bytes

1 byte eliminado gracias a @ Mr.Xcoder

lambda n:sum(n%k<all(k%j for j in range(2,k))for k in range(2,n+1))

Esto agota el tiempo para los casos de prueba más grandes. Pruébalo en línea!

Números R +, 30 14 bytes

16 bytes eliminados gracias a @Giuseppe

numbers::omega

Además, aquí está el ¡ Pruébalo en línea! enlace por @Giuseppe.

Convexo , 3 bytes

mF,

Pruébalo en línea!

Pari / GP , 5 bytes

No sé por qué se llama nu en Mathematica pero omega en Pari / GP.

omega

Pruébalo en línea!

Haskell , 58 bytes

-4 bytes gracias a @Laikoni

f n=sum[1|x<-[2..n],gcd x n>1,all((>)2.gcd x)[2..x-1]]

Pruébalo en línea!

Explicación

Esencialmente genera todos los primos como máximo ny los filtra por ser un factor de n y luego toma la longitud del resultado.

f n=                                                   -- main function
    sum[                                             ] -- output the length of the list
        1|x<-[2..n],                                   -- consider all potential primes <=n
                                                       -- and insert 1 into the list if predicates are satisfied
                    gcd x n>1,                         -- which are a factor of n
                              all(          )[2..x-1]  -- and for which all smaller numbers satisfy
                                  (>)2.                -- 2 being larger than
                                       gcd x           -- the gcd of x with the current smaller number

Japt, 5 4 bytes

â èj

Intentalo

Obtenga los divisores ( â) y cuente ( è) los primos ( j).

ARBLE , 28 bytes

len(unique(primefactors(n)))

Pruébalo en línea!

Esta es una solución muy literal.

Dyalog APL , 17 bytes

⎕CY'dfns'
≢∪3pco⎕

Pruébalo en línea!

Python 2 ,  63  55 bytes

^{Una respuesta mucho más interesante ...}

-8 bytes gracias a Jonathan Frech (¡use un argumento con un valor predeterminado para el ajuste posterior del resultado de primos de 0a 1- mucho mejor que una lambda envolvente!)

f=lambda n,o=1:sum(n%i+f(i,0)<1for i in range(2,n))or o

Una función recursiva que toma un entero positivo n, y devuelve un entero positivo, el conteo.

Pruébalo en línea! Realmente ineficiente, ni siquiera se moleste con los otros casos de prueba.

J, 12 bytes

{:@$@(__&q:)

q: es la función de exponentes primos de J, dándole el argumento __ produce una matriz cuya primera fila son todos factores primos distintos de cero y cuya segunda fila son sus exponentes.

Tomamos la forma $de esa matriz, filas por columnas, el número de columnas es la respuesta que buscamos.

{: nos da el último elemento de esta lista de dos elementos (filas numéricas, columnas numéricas) y, por lo tanto, la respuesta.

Pruébalo en línea!

Java (OpenJDK 9) , 67 bytes

n->{int c=0,p=1;for(;p<n;)if(n%++p<1)for(c++;n%p<1;n/=p);return c;}

Pruébalo en línea!

Javascript ES6, 56 caracteres

n=>eval(`for(q=2,r=0;q<=n;++q)n%q||(n/=q,r+=!!(n%q--))`)

Prueba:

f=n=>eval(`for(q=2,r=0;q<=n;++q)n%q||(n/=q,r+=!!(n%q--))`)
console.log([24,126,1538493,123456].map(f)=="2,3,4,3")