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 code-golf , le score le plus bas en octets gagne!

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)

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

Mathematica, 7 octets

PrimeNu

Ouais, il y a un intégré.

Mathematica, 21 octets

Length@*FactorInteger

Le long chemin.

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.

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]

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 .

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

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

Ohm v2 , 2 octets

ml

Essayez-le en ligne!

Les deux fonctions intégrées sont côte à côte dans la documentation lol.

Gelée , 2 octets

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

Æv

Essayez-le en ligne!

Un intégré.

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.

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

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

Brachylog , 3 octets

ḋdl

Essayez-le en ligne!

Explication

ḋ      Prime decomposition
 d     Remove duplicates
  l    Length

Pyth, 3 octets

l{P

Suite de tests

Length (l) of set ({) of prime factors (P) of the input.

Husk, 3 bytes

Lup

Try it online!

Explanation

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

Actually, 2 bytes

^{Yet another pretty boring answer... --- J. Allan}

yl

Try it online!

The first character can be replaced by w.

Pyke, 3 bytes

P}l

Try it here!

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!

R + numbers, 30 14 bytes

16 bytes removed thanks to @Giuseppe

numbers::omega

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

Convex, 3 bytes

mF,

Try it online!

Pari/GP, 5 bytes

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

omega

Try it online!

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

Japt, 5 4 bytes

â èj

Try it

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

ARBLE, 28 bytes

len(unique(primefactors(n)))

Try it online!

This is a very literal solution

Dyalog APL, 17 bytes

⎕CY'dfns'
≢∪3pco⎕

Try it online!

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.

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!

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

Try it online!

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