Les amorces dans la factorisation première

9

J'ai vu un autre défi majeur arriver dans PPCG, et je m'aime quelques premiers. Ensuite, j'ai mal lu le texte d'introduction et je me suis demandé ce que les cerveaux créatifs avaient trouvé ici.

Il s'avère que la question posée était triviale, mais je me demande si c'est la même chose pour la question que j'ai (mal) lue:

6 peut être représenté par 2 ^ 1 * 3 ^ 1, et 50 peut être représenté par 2 ^ 1 * 5 ^ 2 (où ^ indique l'exonération).

Ta tâche:

Écrivez un programme ou une fonction pour déterminer le nombre de nombres premiers distincts dans cette représentation d'un nombre.

Contribution:

Un entier n tel que 1 <n <10 ^ 12, pris par n'importe quelle méthode normale.

Production:

Le nombre de nombres premiers distincts qui sont requis pour représenter les facteurs premiers uniques de n.

Cas de test:

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)

Ce n'est pas une séquence OEIS.

Notation:

C'est le code-golf , le score le plus bas en octets gagne!

code-golf math primes integer pbeentje
la source
Quel est le résultat attendu 64? Est-ce 2 (2,3)(comme 6 peut être représenté comme 2 * 3) ou 1 (2)(ignorez le 6)?
Emigna
pour 64le résultat attendu est 1 (2). J'aime l'idée de le faire récursivement, mais ce n'est pas ainsi que je lis la question d'origine. Je pensais que 8640c'était un cas de test approprié, mais aurait dû être plus explicite - merci.
pbeentje
Vous prétendez que ce n'est pas une séquence OEIS. N'est-ce pas A001221, les valeurs de la (petite) fonction oméga?
Gray Taylor
A001221 est similaire, mais commence à diverger aux termes 8 et 9 (ici 2, A001221 1) en raison de l'inclusion de l'exposant comme premier élément dans cet exercice.
pbeentje
Ah, je vois. Notez la factorisation des nombres premiers, puis voyez combien de nombres premiers différents j'ai écrits (quel que soit le rôle qu'ils ont joué). Je me demande ce qui se passe si vous allez plus loin et factorisez l'exposant ...
Gray Taylor

Réponses:

5

Mathematica, 39 octets

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

Essayez-le en ligne!

merci à Martin Ender (-11 octets)

J42161217
la source
Casess'avère être plus court que Select(-4 octets): Tr[1^Union@Cases[FactorInteger@#,_?PrimeQ,2]]&(passe tous les cas de test sur un nouveau noyau)
JungHwan Min
Et alors Count[Union@@FactorInteger@#,_?PrimeQ]&? (N'ont pas vérifié tous les cas de test.)
Martin Ender
@MartinEnder semble que cela devrait fonctionner. Réussit également tous les cas de test.
JungHwan Min
5

05AB1E , 9 7 octets

Enregistré 2 octets grâce à Kevin Cruijssen

ÓsfìÙpO

Essayez-le en ligne!

Explication

Ó        # 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
la source
1
-1 octet en utilisant €pOaprès avoir fusionné les facteurs premiers et les exposants:ÓsfìÙ€pO
Kevin Cruijssen
@KevinCruijssen: Merci! Enregistre réellement 2 car €n'est pas nécessaire.
Emigna
Ah, bien sûr .. Wow, je ne sais pas comment j'ai raté ça, haha ​​xD
Kevin Cruijssen
4

Gelée ,  9  7 octets

ÆFFQÆPS

Essayez-le en ligne! ou Découvrez la suite de tests.

Comment?

ÆFFQÆPS ~ Programme complet.

ÆF ~ Factorisation première en paires [prime, exposant].
  F ~ Aplatir.
   Q ~ Dédupliquer.
    ÆP ~ Pour chacun, vérifiez s'il est premier. 1 si Vrai, 0 si Faux.
      S ~ Sum.
M. Xcoder
la source
4

Gaia , 6 octets

ḋ_uṗ¦Σ

Essayez-le en ligne!

  • ḋ calcule la factorisation principale, sous forme de paires [prime, exposant] .

  • _ aplatit la liste.

  • u supprime les éléments en double.

  • ṗ¦mappe à travers les éléments et renvoie 1 si un nombre premier est trouvé, 0 sinon.

  • Σ résume la liste.

M. Xcoder
la source
3

CJam (13 octets)

{mFe__&:mp1b}

Suite de tests en ligne

C'est assez simple: obtenir des nombres premiers avec des multiplicités, réduire à des valeurs distinctes, filtrer les nombres premiers, compter.

Malheureusement, Martin a souligné certains cas qui n'ont pas été traités par l'astuce légèrement intéressante dans ma réponse originale, bien qu'il ait également fourni une économie d'un octet en observant que depuis mpdonne 0ou 1peut être mappé plutôt que filtré.

Peter Taylor
la source
2

Ohm v2 , 6 5 octets

-1 octet grâce à @ Mr.Xcoder

ä{UpΣ

Essayez-le en ligne!

Cinaski
la source
5 octets:ä{UpΣ
M. Xcoder
@ Mr.Xcoder Merci! Je cherchais cette fonction intégrée mais je n'ai pas pu la trouver ..
Cinaski
1

En fait , 7 octets

w♂i╔♂pΣ

Essayez-le en ligne!

Explication:

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
la source
1

Python 2 , 142 135 119 119 octets

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

Essayez-le en ligne!

ovs
la source
1

Husk ,  11  10 octets

#ṗuS+omLgp

Essayez-le en ligne!

EDIT: enregistré 1 octet grâce à Zgarb .

M. Xcoder
la source
1
#ṗuS+omLgpenregistre un octet.
Zgarb
1

Brachylog , 7 octets

ḋọcdṗˢl

Essayez-le en ligne!

           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.

Une version amusante de 9 octets: ḋọ{∋∋ṗ}ᶜ¹

Chaîne indépendante
la source
0

Numéros R +, 92 octets

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

Essayez-le en ligne!

Giuseppe
la source
0

J, 20 octets

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

Compté à la main lol, alors dites-moi si cela ne fonctionne pas.

Des suggestions de golf?

Soumission ennuyeuse: aplatissez la table de factorisation des nombres premiers et comptez les nombres premiers.

cole
la source
0

Javascript (ES6), 145 octets

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
la source