Eine Möglichkeit, eine natürliche Zahl darzustellen, besteht darin, Exponenten von Primzahlen zu multiplizieren. Zum Beispiel kann 6 durch 2 ^ 1 * 3 ^ 1 dargestellt werden und 50 kann durch 2 ^ 1 * 5 ^ 2 dargestellt werden (wobei ^ die Exponierung anzeigt). Die Anzahl der Primzahlen in dieser Darstellung kann dazu beitragen, festzustellen, ob die Verwendung dieser Darstellungsmethode im Vergleich zu anderen Methoden kürzer ist. Da ich diese aber nicht von Hand berechnen möchte, brauche ich ein Programm, das das für mich erledigt. Da ich mir das Programm jedoch merken muss, bis ich nach Hause komme, muss es so kurz wie möglich sein.

Deine Aufgabe:

Schreiben Sie ein Programm oder eine Funktion, um zu bestimmen, wie viele verschiedene Primzahlen in dieser Darstellung einer Zahl enthalten sind.

Eingang:

Eine ganze Zahl n mit 1 <n <10 ^ 12, die mit einer normalen Methode ermittelt wird.

Ausgabe:

Die Anzahl der unterschiedlichen Primzahlen, die für die Darstellung der Eingabe erforderlich sind, wie in der Einführung erläutert.

Testfälle:

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)

Dies ist OEIS A001221 .

Wertung:

Dies ist Code-Golf , die niedrigste Punktzahl in Bytes gewinnt!

MATL , 4 3 Bytes

-1 Byte dank Luis Mendo

YFz

Probieren Sie es online!

YF         Exponents of prime factors
  z        Number of nonzeros

Ursprüngliche Antwort:

Yfun

Probieren Sie es online!

Eine sehr gute YfunAntwort.

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

05AB1E , 2 Bytes

^{eine weitere ziemlich langweilige Antwort ...}

fg

Ein vollständiges Programm, das eine numerische Eingabe akzeptiert und das Ergebnis druckt

Probieren Sie es online!

Wie?

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

Mathematica, 7 Bytes

PrimeNu

Ja, da ist ein eingebautes.

Mathematica, 21 Bytes

Length@*FactorInteger

Der weite Weg.

Gaia , 2 Bytes

^{Noch eine ziemlich langweilige Antwort ... --- J. Allan}

ḋl

Probieren Sie es online!

• ḋ- Primfaktorisierung als [Prim, Exponent] -Paare.

• l - Länge.

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

Die Eingabe ist unär.

Vielen Dank an @MartinEnder für das Golfen von 1 Byte!

Probieren Sie es online! (einschließlich Dezimal-Unär-Umrechner)

Wie es funktioniert

Da das Programm aus einem einzelnen regulären Ausdruck mit dem &Modifikator besteht, zählt Retina einfach die Anzahl überlappender Übereinstimmungen. Es wird angenommen, dass die Eingabe aus n Wiederholungen von 1 besteht und nichts anderem besteht.

Der negative Ausblick

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

an Stellen Einstimmungen zwischen 1 s, die nicht von zwei oder mehr gefolgt 1 s '( 11+), gefolgt durch eine oder mehr Wiederholungen der gleichen Menge an 1 ‚s ( \1+), durch das Ende der Eingabe folgt ( $).

Jede zusammengesetzte Zahl ab mit a, b> 1 kann geschrieben werden als b Wiederholungen eine Wiederholung von 1 , so dass die Look - Ahead - Standorten entspricht nur gefolgt von p Wiederholungen von 1 , wobei p = 1 oder p ist eine Primzahl.

Der Regex

(11+)$

stellt sicher , p> 1 durch mindestens zwei bedürftigen 1 ‚s ( 11+) und speichert der Schwanz von 1 ‘ in der zweiten Einfanggruppe s ( \2).

Endlich der positive Lookbehind

(?<=^\2+)

überprüft, ob die gesamte Eingabe aus kp Vorkommen ( k ≥ 1 ) von 1 besteht , und überprüft, ob p die Eingabe teilt.

Somit entspricht jede Übereinstimmung einem eindeutigen Primteiler p .

Bash + GNU-Dienstprogramme, 33

• Dank @Dennis 1 Byte gespart

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

Probieren Sie es online aus .

Erläuterung

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

Gelee , 3 Bytes

^{eine ziemlich langweilige Antwort ...}

ÆFL

Ein monadischer Link, der eine Nummer aufnimmt und eine Nummer zurückgibt

Probieren Sie es online!

Wie?

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

Ohm v2 , 2 Bytes

ml

Probieren Sie es online!

Die beiden eingebauten Funktionen befinden sich in der Dokumentation lol direkt nebeneinander.

Gelee , 2 Bytes

^{Noch eine ziemlich langweilige Antwort ... --- J. Allan}

Æv

Probieren Sie es online!

Ein eingebautes.

Alice , 10 Bytes

/o
\i@/Dcd

Probieren Sie es online!

Erläuterung

/o
\i@/...

Dies ist nur das Standardframework für lineare arithmetisch anspruchsvolle Programme, die dezimale E / A benötigen. Das eigentliche Programm selbst ist dann nur:

Dcd

Welches tut:

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

* Für @SEJPM fordern Sie eine Erklärung an: Was ich hier tue, ist, dass ich von 2 - n gehe (was sich ändert und schließlich der größte Primfaktor sein wird) - jetzt, wenn die aktuelle Zahlenteilung ni es nur einmal zählen möchte (gerade) obwohl es ein Faktor von 2 * 2 * 2 * 3 sein kann - 2 wird einmal gezählt) - so kommt das "j" zum Bild, wenn j im Aufruf der Funktion nicht angegeben ist - j erhält den Wert von " undefined ", und wenn n% i == 0, dann rufe ich die Funktion mit j = 1 beim nächsten Aufruf auf) - und dann addiere ich nur 1, wenn j gleich undefined ist, was! j + Funktion ist (n / i, i, ( j = 1 oder nur 1)). ich ändere i in dieser Angelegenheit nicht, weil es noch durch i wieder teilbar sein kann (2 * 2 * 3), aber dann wird j gleich 1 und es wird nicht als ein Faktor gezählt. Ich hoffe, ich habe es gut genug erklärt.

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

Wenn die letzte Primzahl sehr groß ist, hat sie einen maximalen Aufrufstapel. Wenn dies ein Problem ist, kann ich eine iterative ausführen

CJam , 7 5 Bytes

Danke an Martin Ender für 2 Bytes!

{mF,}

Anonymer Block (Funktion), der die Eingangsnummer auf dem Stapel erwartet und durch die Ausgangsnummer ersetzt.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

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

Brachylog , 3 Bytes

ḋdl

Probieren Sie es online!

Erläuterung

ḋ      Prime decomposition
 d     Remove duplicates
  l    Length

Pyth, 3 bytes

l{P

Test suite

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