Uma maneira de representar um número natural é multiplicando expoentes de números primos. Por exemplo, 6 podem ser representados por 2 ^ 1 * 3 ^ 1 e 50 podem ser representados por 2 ^ 1 * 5 ^ 2 (onde ^ indica exponência). O número de primos nessa representação pode ajudar a determinar se é mais curto usar esse método de representação, em comparação com outros métodos. Mas como não quero calculá-las manualmente, preciso de um programa para fazer isso por mim. No entanto, como terei que me lembrar do programa até chegar em casa, ele deve ser o mais curto possível.

Sua tarefa:

Escreva um programa ou função para determinar quantos primos distintos existem nessa representação de um número.

Entrada:

Um número inteiro n tal que 1 <n <10 ^ 12, obtido por qualquer método normal.

Resultado:

O número de primos distintos necessários para representar a entrada, conforme descrito na introdução.

Casos de teste:

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 é o OEIS A001221 .

Pontuação:

Isso é código-golfe , a menor pontuação em bytes ganha!

MATL , 4 3 bytes

-1 byte graças a Luis Mendo

YFz

Experimente online!

YF         Exponents of prime factors
  z        Number of nonzeros

Resposta original:

Yfun

Experimente online!

Uma Yfunresposta ver .

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

05AB1E , 2 bytes

^{outra resposta muito chata ...}

fg

Um programa completo que aceita uma entrada numérica e imprime o resultado

Experimente online!

Quão?

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

Mathematica, 7 bytes

PrimeNu

Sim, há um embutido.

Mathematica, 21 bytes

Length@*FactorInteger

O longo caminho.

Gaia , 2 bytes

^{Ainda outra resposta bastante chata ... --- J. Allan}

ḋl

Experimente online!

• ḋ- Fatoração primária como pares [primos, expoentes] .

• l - Comprimento.

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+)

A entrada está unária.

Obrigado a @MartinEnder pelo golfe de 1 byte!

Experimente online! (inclui conversor decimal para unário)

Como funciona

Como o programa consiste em uma única regex com o &modificador, o Retina simplesmente conta a quantidade de correspondências sobrepostas . Supõe-se que a entrada consiste em n repetições de 1 e nada mais.

O lookahead negativo

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

partidas em locais entre 1 's que são não seguidos por duas ou mais 1 ' s ( 11+), seguido por uma ou mais repetições da mesma quantidade de 1 's ( \1+), seguindo-se a extremidade de entrada ( $).

Qualquer número composto ab com a, b> 1 pode ser escrito como b repetições de uma repetição de 1 ; portanto, o lookahead corresponde apenas a locais seguidos de p repetições de 1 , onde p = 1 ou p é primo.

O regex

(11+)$

torna-se p> 1 , exigindo que pelo menos dois 1 's ( 11+) e armazena a cauda de 1 está no segundo grupo de captura ( \2).

Finalmente, o olhar positivo por trás

(?<=^\2+)

verifica se a entrada inteira consiste em ocorrências de kp ( k ≥ 1 ) de 1 , verificando se p divide a entrada.

Assim, cada correspondência corresponde a um divisor principal exclusivo p .

Utilitários Bash + GNU, 33

• 1 byte salvo graças a @Dennis

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

Experimente online .

Explicação

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

Geléia , 3 bytes

^{uma resposta bastante chata ...}

ÆFL

Um link monádico pegando um número e retornando um número

Experimente online!

Quão?

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

Ohm v2 , 2 bytes

ml

Experimente online!

Os dois built-ins estão próximos um do outro na documentação lol.

Gelatina , 2 bytes

^{Ainda outra resposta bastante chata ... --- J. Allan}

Æv

Experimente online!

Um embutido.

Alice , 10 bytes

/o
\i@/Dcd

Experimente online!

Explicação

/o
\i@/...

Essa é apenas a estrutura padrão para programas aritméticos pesados ​​lineares que precisam de E / S decimal. O programa atual é então apenas:

Dcd

O que faz:

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 o @SEJPM, solicite uma explicação: o que estou fazendo aqui é passar de 2 - n (que muda e, eventualmente, será o maior fator primordial) - agora, se a divisão do número atual ni quiser contar apenas uma vez (mesmo embora possa ser um fator de 2 * 2 * 2 * 3-2 é contado uma vez) - então o "j" aparece na imagem, quando j não é especificado na chamada da função - j receberá o valor de " undefined ", e quando n% i == 0, chamo a função com j = 1 na próxima chamada) - e adiciono apenas 1 quando j é igual a undefined, que é! j + Function (n / i, i, ( j = 1 ou apenas 1)). não mudo i nesse assunto, pois ainda pode ser divisível por i novamente (2 * 2 * 3), mas j será igual a 1 e não será considerado um fator. Espero que eu tenha explicado bem o suficiente.

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);

Se o último primo for muito grande, ele terá uma pilha máxima de chamadas - se for um problema, eu posso criar um iterativo

CJam , 7 5 bytes

Obrigado a Martin Ender por 2 bytes de desconto!

{mF,}

Bloco anônimo (função) que espera o número de entrada na pilha e o substitui pelo número de saída.

Experimente online! Ou verifique todos os casos de teste .

Explicação

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

Braquilog , 3 bytes

ḋdl

Experimente online!

Explicação

ḋ      Prime decomposition
 d     Remove duplicates
  l    Length

Pitão, 3 bytes

l{P

Suíte de teste

Comprimento ( l) do conjunto ( {) de fatores primos ( P) da entrada.

Casca , 3 bytes

Lup

Experimente online!

Explicação

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

Na verdade , 2 bytes

^{Ainda outra resposta bastante chata ... --- J. Allan}

yl

Experimente online!

O primeiro caractere pode ser substituído por w.

Pyke , 3 bytes

P}l

Experimente aqui!

Python 3 , 68 67 bytes

1 byte removido graças a @ Mr.Xcoder

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

Isso expira nos maiores casos de teste. Experimente online!

Números R +, 30 14 bytes

16 bytes removidos graças a @Giuseppe

numbers::omega

Além disso, aqui está o Experimente online !! link para @ Giuseppe.

Convexo , 3 bytes

mF,

Experimente online!

Pari / GP , 5 bytes

Não sei por que é chamado nu no Mathematica, mas ômega no Pari / GP.

omega

Experimente online!

Haskell , 58 bytes

-4 bytes graças a @Laikoni

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

Experimente online!

Explicação

Essencialmente, gera todos os números primos no máximo ne os filtra por serem um fator de n e, em seguida, leva a duração do 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

Tente

Obtenha os divisores ( â) e conte ( è) os primos ( j).

ARBLE , 28 bytes

len(unique(primefactors(n)))

Experimente online!

Esta é uma solução muito literal

Dyalog APL , 17 bytes

⎕CY'dfns'
≢∪3pco⎕

Experimente online!

Python 2 ,  63  55 bytes

^{Uma resposta muito mais interessante ...}

-8 bytes graças a Jonathan Frech (use um argumento com um padrão para o pós-ajuste do resultado de primos de 0para 1- muito melhor que um lambda de empacotamento !!)

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

Uma função recursiva que pega um número inteiro positivo ne retorna um número inteiro positivo, a contagem.

Experimente online! Realmente ineficiente, nem se preocupe com os outros casos de teste.

J, 12 bytes

{:@$@(__&q:)

q:é a função de expoentes primários de J, fornecendo a ele o argumento que __produz uma matriz cuja primeira linha é todos os fatores primos diferentes de zero e cuja segunda linha é seus expoentes.

Tomamos a forma $dessa matriz - linhas por colunas - o número de colunas é a resposta que buscamos.

{: nos fornece o último item desses dois itens (num linhas, num colunas) e, portanto, a resposta.

Experimente online!

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;}

Experimente online!

Javascript ES6, 56 caracteres

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

Teste:

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")