Combien de nombres premiers uniques?

14

Une façon de représenter un nombre naturel consiste à multiplier les exposants des nombres premiers. Par exemple, 6 peut être représenté par 2 ^ 1 * 3 ^ 1, et 50 peut être représenté par 2 ^ 1 * 5 ^ 2 (où ^ indique une exponention). Le nombre de nombres premiers dans cette représentation peut aider à déterminer s'il est plus court d'utiliser cette méthode de représentation, par rapport à d'autres méthodes. Mais parce que je ne veux pas les calculer à la main, j'ai besoin d'un programme pour le faire pour moi. Cependant, parce que je devrai me souvenir du programme jusqu'à mon retour à la maison, il doit être aussi court que possible.

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 l'entrée, comme indiqué dans l'introduction.

Cas de test:

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)

Il s'agit d' OEIS A001221 .

Notation:

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

Gryphon
la source
3
Tant de questions principales récemment! J'aime cela.
Giuseppe
2
En relation
M. Xcoder
3
La raison derrière le downvote pourrait être sa trivialité. Pour autant que je puisse voir, il y a 3 situations en ce qui concerne les langues de golf: 1. intégré 2. chaîne de deux intégrés 3. chaîne de 3 intégrés (j'ai personnellement trois réponses de 2 octets); Je ne sais pas si c'est une bonne raison pour un downvote, mais c'est une cause possible
M. Xcoder
1
Peut-être, mais j'apprécierais que l'un des trois électeurs baissiers m'ait dit cela. Bien qu'il soit trivial dans les langues de golf, il existe quelques solutions intéressantes dans les langues non golfiques, qui sont celles que je voulais voir lorsque j'ai posté ce défi. Après tout, il existe de nombreux défis sur le site qui sont triviaux pour les golflangs, mais produisent des solutions intéressantes non-golflang.
Gryphon
1
Il serait avantageux d'inclure un nombre premier dans les cas de test. De plus, certaines langues / approches sont difficiles à tester pour de grands nombres. Quelques cas de test plus petits seraient bien.
Dennis

Réponses:

6

MATL , 4 3 octets

-1 octet grâce à Luis Mendo

YFz

Essayez-le en ligne!

YF         Exponents of prime factors
  z        Number of nonzeros

Réponse originale:

Yfun

Essayez-le en ligne!

Une vraie Yfunréponse.

          (Implicit input)
Yf         Prime factorization
  u        Unique
   n       Numel
           (Implicit output)
Giuseppe
la source
1
Pourquoi s'amuser? - ;-)
Adam
1
Barré 4 est toujours régulier 4
Gryphon
5

05AB1E , 2 octets

une autre réponse assez ennuyeuse ...

fg

Un programme complet acceptant une entrée numérique et imprimant le résultat

Essayez-le en ligne!

Comment?

fg - implicitly take input
f  - get the prime factors with no duplicates
 g - get the length
   - implicit print
Jonathan Allan
la source
5

Mathematica, 7 octets

PrimeNu

Ouais, il y a un intégré.

Mathematica, 21 octets

Length@*FactorInteger

Le long chemin.

Misha Lavrov
la source
Quelle est la raison de l'astérisque? N'est-ce pas Length@FactorIntegerpareil?
numbermaniac
1
Length@*FactorIntegerproduit une fonction pure: la composition de Lengthet FactorInteger. Je peux définir fun=Length@*FactorIntegerpuis appeler fun[1001]. D'un autre côté, Length@FactorIntegersignifierait Length[FactorInteger]et évaluerait 0.
Misha Lavrov du
5

Gaia , 2 octets

Encore une autre réponse assez ennuyeuse ... --- J. Allan

ḋl

Essayez-le en ligne!

  • - Factorisation principale sous forme de paires [prime, exposant] .

  • l - Longueur.

M. Xcoder
la source
4

Python 2, 56 octets

f=lambda n,p=2,k=1:n/p and[f(n,p+1),k+f(n/p,p,0)][n%p<1]
orlp
la source
Est-ce un port de la réponse de Dennis ici par hasard?
Jonathan Allan
1
@JonathanAllan Oui, modifié à la place pour compter les facteurs premiers uniques.
orlp
4

Rétine , 31 30 octets

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

L'entrée est unaire.

Merci à @MartinEnder pour le golf de 1 octet!

Essayez-le en ligne! (comprend un convertisseur décimal-unaire)

Comment ça fonctionne

Étant donné que le programme se compose d'une seule expression régulière avec le &modificateur, Retina compte simplement le nombre de correspondances qui se chevauchent . L'entrée est supposée être constituée de n répétitions de 1 et rien d'autre.

L'anticipation négative

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

correspond à des emplacements entre 1 qui ne sont pas suivis par deux ou plusieurs 1 ( 11+), suivis par une ou plusieurs répétitions du même montant de 1 ( \1+), suivis de la fin de la saisie ( $).

Tout nombre composite ab avec a, b> 1 peut être écrit comme b répétitions d' une répétition de 1 , de sorte que l'antichambre ne correspond qu'à des emplacements suivis de p répétitions de 1 , où p = 1 ou p est premier.

Le regex

(11+)$

s'assure que p> 1 en exigeant au moins deux 1 ( 11+) et stocke la queue de 1 dans le deuxième groupe de capture ( \2).

Enfin, le regard positif derrière

(?<=^\2+)

vérifie que l'entrée entière consiste en kp occurrences ( k ≥ 1 ) de 1 , vérifiant que p divise l'entrée.

Ainsi, chaque correspondance correspond à un diviseur premier unique p .

Dennis
la source
4

Utilitaires Bash + GNU, 33

  • 1 octet enregistré grâce à @Dennis
factor|grep -Po ' \d+'|uniq|wc -l

Essayez-le en ligne .

Explication

factor|                            # Split input into prime factors
       grep -Po ' \d+'|            # group factors onto lines
                       uniq|       # remove duplicates
                            wc -l  # count the lines
Traumatisme numérique
la source
1
grep -Po ' \d+'enregistre un octet de plus tr \ \\n|sed 1d.
Dennis
Malheureusement, grep -Po '( \d+)\1*'échoue pour l'entrée 46 .
Dennis
@Dennis thanks - Je l'ai corrigé en utilisant votre suggestion d'origine
Digital Trauma
3

Gelée , 3 octets

une réponse assez ennuyeuse ...

ÆFL

Un lien monadique prenant un numéro et renvoyant un numéro

Essayez-le en ligne!

Comment?

ÆFL - Link: number, n
ÆF  - prime factorisation as a list of prime, exponent pairs
  L - length
Jonathan Allan
la source
1
Comment avez - vous manqué Æv?
mon pronom est monicareinstate
C'était facile - je ne l'ai jamais utilisé et je n'ai pas cherché dans la liste sur le wiki.
Jonathan Allan
Comment tapez-vous des caractères de gelée sans liste d'atomes et liste de quicks?
mon pronom est monicareinstate
1. Æest le code alt 0198. 2. Vous pouvez configurer un clavier (je ne l'ai pas). 3. La page de codes.
Jonathan Allan
3

Gelée , 2 octets

Encore une autre réponse assez ennuyeuse ... --- J. Allan

Æv

Essayez-le en ligne!

Un intégré.

M. Xcoder
la source
3

Alice , 10 octets

/o
\i@/Dcd

Essayez-le en ligne!

Explication

/o
\i@/...

Il s'agit simplement du cadre standard pour les programmes linéaires lourds en arithmétique qui nécessitent des E / S décimales. Le programme lui-même n'est alors que:

Dcd

Qui fait:

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.
Martin Ender
la source
3

JavaScript 45 octets

* Pour @SEJPM, demandez une explication: ce que je fais ici est ceci - je vais de 2 - n (qui change, et sera finalement le plus grand facteur premier) - maintenant si le nombre actuel ne divise ni ne veut le compter qu'une seule fois (même bien qu'il puisse être un facteur de 2 * 2 * 2 * 3 - 2 est compté une fois) - donc le "j" vient à l'image, quand j n'est pas spécifié dans l'appel de la fonction - j recevra la valeur de " undefined ", et quand n% i == 0 alors j'appelle la fonction avec j = 1 dans le prochain appel) - et puis j'ajoute seulement 1 quand j est égal à undefined qui est! j + Function (n / i, i, ( j = 1 ou juste 1)). je ne change pas i dans ce domaine car il peut encore être divisible par i (2 * 2 * 3) mais alors j sera égal à 1 et il ne comptera pas comme un facteur. j'espère que je l'ai expliqué assez 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 le dernier nombre premier est très grand, il aura une pile d'appels maximale - si c'est un problème, je peux en faire un itératif

DanielIndie
la source
Pourriez-vous écrire une explication de cette réponse? Il semble utiliser une approche habituelle du reste des réponses.
SEJPM
@SEJPM j'ai ajouté quelques explications
DanielIndie
1
Pour info, nous pouvons supposer des piles d'appels infinies / des ressources infinies pour la majorité des défis de golf de code (essentiellement sauf si la question indique le contraire).
Jonathan Allan
3

CJam , 7 5 octets

Merci à Martin Ender pour 2 octets!

{mF,}

Bloc anonyme (fonction) qui attend le numéro d'entrée sur la pile et le remplace par le numéro de sortie.

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

{   }   e# Define block
 mF     e# List of (prime, exponent) pairs
   ,    e# Length
Luis Mendo
la source
2

Husk, 3 bytes

Lup

Try it online!

Explanation

  p  -- prime factors
 u   -- unique elements
L    -- length
ბიმო
la source
2

Actually, 2 bytes

Yet another pretty boring answer... --- J. Allan

yl

Try it online!

The first character can be replaced by w.

Mr. Xcoder
la source
That's enough, dude... :P
totallyhuman
@icrieverytim I promise this is my last golfing-language answer (I only have 4 :P)
Mr. Xcoder
2

Python 3, 68 67 bytes

1 byte removed thanks to @Mr.Xcoder

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

This times out for the largest test cases. Try it online!

Luis Mendo
la source
67 bytes
Mr. Xcoder
2

R + numbers, 30 14 bytes

16 bytes removed thanks to @Giuseppe

numbers::omega

Also, here is the Try it online!! link per @Giuseppe.

Joseph Wood
la source
You may omit the f=function(x) and the (x) as numbers::omega is a function already. However, as numbers is not standard for R, you should make your answer "R + numbers". Also, you should include a TIO link. Still, +1, very nice.
Giuseppe
@Giuseppe, you are too nice. Thanks for your help. BTW, in addition to some of your insightful answers, I checked out Tips for golfing in R, as you suggested. There are some real gems there. Anywho, I will update my answer with your recommendations. Also, your MATL solution is very nice (+1 yesterday).
Joseph Wood
NP, feel free to ping me in chat or comment on an answer of mine if you have questions.
Giuseppe
@Giuseppe is there a meta consensus on needing to explicitly state "R + numbers"? It seems like if we state the additional package then we should be able to save the bytes of explicitly calling it with numbers::. Otherwise, to me it's the same as using an import in any other language.
BLT
(scrolls down and sees a python example of this...) I guess I'm wondering about a broader meta consensus, then. It just sort of seems silly to me.
BLT
1

Pari/GP, 5 bytes

I don't know why it is called nu in Mathematica but omega in Pari/GP.

omega

Try it online!

alephalpha
la source
1

Haskell, 58 bytes

-4 bytes thanks to @Laikoni

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

Try it online!

Explanation

Essentially generates all primes at most as large as n and filters them for being a factor of n and then takes the length of the result.

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
SEJPM
la source
You can use sum[1|x<- ... ] instead of length.
Laikoni
1

Japt, 5 4 bytes

â èj

Try it

Get the divisors (â) and count (è) the primes (j).

Shaggy
la source
1

ARBLE, 28 bytes

len(unique(primefactors(n)))

Try it online!

This is a very literal solution

ATaco
la source
I was looking at this and going "Hey, wait a minute, this is a snippet!" And then I see... is this supposed to be a non-esoteric language with implicit IO?!
totallyhuman
@icrieverytim Congratulations, you have discovered one of the main reasons this language exists.
ATaco
0

Python 2,  63  55 bytes

A much more interesting answer...

-8 bytes thanks to Jonathan Frech (use an argument with a default for the post-adjustment of the result of primes from 0 to 1 -- much better than a wrapping lambda!!)

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

A recursive function taking a positive integer, n, and returning a positive integer, the count.

Try it online! Really inefficient, don't even bother with the other test cases.

Jonathan Allan
la source
55 bytes.
Jonathan Frech
@JonathanFrech Thanks, that is much cleaner.
Jonathan Allan
0

J, 12 bytes

{:@$@(__&q:)

q: is J's prime exponents function, giving it the argument __ produces a matrix whose first row is all nonzero prime factors and whose 2nd row is their exponents.

We take the shape $ of that matrix -- rows by columns -- the number of columns is the answer we seek.

{: gives us the last item of this two items (num rows, num columns) list, and hence the answer.

Try it online!

Jonah
la source
0

Javascript ES6, 56 chars

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

Test:

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

Qwertiy
la source