Primos na fatoração principal

9

Eu vi outro desafio principal chegando no PPCG, e eu me amo alguns números primos. Depois, interpretei mal o texto introdutório e me perguntei o que os cérebros criativos haviam inventado.

Acontece que a pergunta feita foi trivial, mas eu me pergunto se o mesmo se aplica à pergunta que eu (mal) li:

6 pode ser representado por 2 ^ 1 * 3 ^ 1 e 50 pode ser representado por 2 ^ 1 * 5 ^ 2 (onde ^ indica exponência).

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 os fatores primos exclusivos de n.

Casos de teste:

Input      Factorisation      Unique primes in factorisation representation
24         2^3*3^1            2 (2, 3)
126        2^1*3^2*7^1        3 (2, 3, 7)
8          2^3                2 (2, 3)
64         2^6                1 (2) (6 doesn't get factorised further)
72         2^3*3^2            2 (2, 3)
8640       2^6*3^3*5^1        3 (2, 3, 5)
317011968  2^11*3^5*7^2*13^1  6 (2, 3, 5, 7, 11, 13)
27         3^3                1 (3)

Esta não é uma sequência OEIS.

Pontuação:

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

code-golf math primes integer pbeentje
fonte
Qual é o resultado esperado 64? É 2 (2,3)(como 6 pode ser representado como 2 * 3) ou 1 (2)(ignore o 6)?
Emigna
para 64o resultado esperado é 1 (2). Gosto da ideia de fazê-lo recursivamente, mas não é assim que leio a pergunta original. Eu pensei que 8640era um caso de teste adequado, mas deveria ter sido mais explícito - obrigado.
precisa saber é o seguinte
Você alega que essa não é uma sequência OEIS. Não é A001221, os valores da função ômega (pequena)?
Grey Taylor
A001221 é semelhante, mas começa a divergir nos termos 8 e 9 (aqui 2, A001221 1) devido à inclusão do expoente como principal neste exercício.
pbeentje
Ah entendo. Anote a fatoração primária e veja quantos primos diferentes eu escrevi (independentemente do papel que eles desempenharam). Eu me pergunto o que acontece se você ir um passo além e fatorar o expoente ...
Grey Taylor

Respostas:

5

Mathematica, 39 bytes

Count[Union@@FactorInteger@#,_?PrimeQ]&

Experimente online!

graças a Martin Ender (-11 bytes)

J42161217
fonte
Casesacaba por ser mais curto do que Select(-4 bytes): Tr[1^Union@Cases[FactorInteger@#,_?PrimeQ,2]]&(passa todos os casos de teste em um kernel fresco)
JungHwan Min
Que tal Count[Union@@FactorInteger@#,_?PrimeQ]&? (Não têm verificado todos os casos de teste.)
Martin Ender
@MartinEnder parece que deve funcionar. Também passa em todos os casos de teste.
JungHwan Min 10/10
5

05AB1E , 9 7 bytes

Guardado 2 bytes graças a Kevin Cruijssen

ÓsfìÙpO

Experimente online!

Explicação

Ó        # push the prime factor exponents of the input
 sfì     # prepend the prime factors of the input
    Ù    # remove duplicates
     p   # check each if it is prime
      O  # sum
Emigna
fonte
11
-1 byte usando €pOapós mesclar os principais fatores e expoentes:ÓsfìÙ€pO
Kevin Cruijssen
@KevinCruijssen: Obrigado! Na verdade, salva 2, pois €não é necessário.
Emigna 6/05/19
Ah, é claro .. Uau, não sei como eu perdi isso, haha xD
Kevin Cruijssen
4

Geléia ,  9  7 bytes

ÆFFQÆPS

Experimente online! ou Confira o conjunto de teste.

Como?

ÆFFQÆPS ~ Programa completo.

ÆF ~ Fatoração primária como pares [primo, expoente].
  F ~ Achatar.
   Q ~ Desduplicar.
    ÆP ~ Para cada uma, verifique se está pronta. 1 se verdadeiro, 0 se falso.
      S ~ Sum.
Mr. Xcoder
fonte
4

Gaia , 6 bytes

ḋ_uṗ¦Σ

Experimente online!

  • ḋ calcula a fatoração primária, como pares [primo, expoente] .

  • _ nivela a lista.

  • u remove elementos duplicados.

  • ṗ¦mapeia os elementos e retorna 1 se um prime for encontrado, 0 caso contrário.

  • Σ soma a lista.

Mr. Xcoder
fonte
3

CJam (13 bytes)

{mFe__&:mp1b}

Conjunto de testes online

Isso é bem direto: obtenha primos com multiplicidades, reduza a valores distintos, filtre primos, conte.

Infelizmente, Martin apontou alguns casos que não foram tratados pelo truque levemente interessante em minha resposta original, embora ele também tenha proporcionado uma economia de 1 byte, observando que, uma vez que mpdá 0ou 1pode ser mapeado em vez de filtrado.

Peter Taylor
fonte
2

Ohm v2 , 6 5 bytes

-1 byte graças a @ Mr.Xcoder

ä{UpΣ

Experimente online!

Cinaski
fonte
5 bytes:ä{UpΣ
Sr. Xcoder 9/17
@ Mr.Xcoder Obrigado! Eu estava procurando por que built-in mas não foi capaz de encontrá-lo ..
Cinaski
1

Na verdade , 7 bytes

w♂i╔♂pΣ

Experimente online!

Explicação:

w♂i╔♂pΣ
w        factor into [prime, exponent] pairs
 ♂i      flatten to 1D list
   ╔     unique elements
    ♂p   for each element: 1 if prime else 0
      Σ  sum
Mego
fonte
1

Python 2 , 142 135 119 bytes

f=lambda n,d=2:n-1and(n%d and f(n,d+1)or[d]+f(n/d))or[]
p=f(input())
print sum(f(n)==[n]for n in set(p+map(p.count,p)))

Experimente online!

ovs
fonte
1

Braquilog , 7 bytes

ḋọcdṗˢl

Experimente online!

           The output
      l    is the length of
  c        the concatenated
 ọ         list of pairs [value, number of occurrences]
ḋ          from the prime factorization of
           the input
   d       with duplicates removed
    ṗˢ     and non-primes removed.

Uma divertida versão de 9 bytes: ḋọ{∋∋ṗ}ᶜ¹

String não relacionada
fonte
0

Números R +, 92 bytes

function(n)sum(1|unique((x=c((r=rle(primeFactors(n)))$l,r$v))[isPrime(x)]))
library(numbers)

Experimente online!

Giuseppe
fonte
0

J, 20 bytes

3 :'+/1 p:~.,__ q:y'

Contado à mão lol, então me diga se isso está desativado.

Alguma sugestão de golfe?

Submissão chata: achatar a tabela de fatoração principal e contar números primos.

Cole
fonte
0

Javascript (ES6), 145 bytes

n=>{for(a=[b=l=0],q=n,d=2;q>=2;)q%d?(b&&(a.push(0),l++),d++,b=0):(q/=d,a[l]++,b=1);for(i in a){for(d=1,e=a[i];e%d;d++);e-d||n%e&&l++};return l+1}
Naruyoko
fonte