Primzahlen in der Primfaktorisierung

9

Ich habe in PPCG eine weitere Hauptherausforderung gesehen, und ich liebe mich für einige Primzahlen. Dann habe ich den Einführungstext falsch verstanden und mich gefragt, was sich die kreativen Köpfe hier ausgedacht haben.

Es stellt sich heraus, dass die gestellte Frage trivial war, aber ich frage mich, ob dies auch für die Frage gilt, die ich (falsch) gelesen habe:


6 kann durch 2 ^ 1 * 3 ^ 1 dargestellt werden, und 50 kann durch 2 ^ 1 * 5 ^ 2 dargestellt werden (wobei ^ Exponente anzeigt).

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, so dass 1 <n <10 ^ 12, genommen mit einer beliebigen normalen Methode.

Ausgabe:

Die Anzahl der unterschiedlichen Primzahlen, die erforderlich sind, um die eindeutigen Primfaktoren von n darzustellen .

Testfälle:

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)

Dies ist keine OEIS-Sequenz.

Wertung:

Dies ist , niedrigste Punktzahl in Bytes gewinnt!

pbeentje
quelle
Wofür ist das erwartete Ergebnis 64? Ist es 2 (2,3)(da 6 als 2 * 3 dargestellt werden kann) oder 1 (2)(ignorieren Sie die 6)?
Emigna
für 64das erwartete Ergebnis ist 1 (2). Ich mag die Idee, es rekursiv zu machen, aber so lese ich die ursprüngliche Frage nicht. Ich dachte, 8640es wäre ein geeigneter Testfall, hätte aber expliziter sein sollen - danke.
pbeentje
Sie behaupten, dies sei keine OEIS-Sequenz. Ist es nicht A001221, die Werte der (kleinen) Omega-Funktion?
Gray Taylor
A001221 ist ähnlich, beginnt jedoch bei den Begriffen 8 und 9 (hier 2, A001221 1) zu divergieren, da der Exponent als Primzahl in diese Übung einbezogen wird.
pbeentje
Ah ich sehe. Schreiben Sie die Primfaktorisierung auf und sehen Sie dann, wie viele verschiedene Primzahlen ich geschrieben habe (unabhängig von der Rolle, die sie gespielt haben). Ich frage mich, was passiert, wenn Sie einen Schritt weiter gehen und den Exponenten faktorisieren ...
Gray Taylor

Antworten:

5

Mathematica, 39 Bytes

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

Probieren Sie es online aus!

danke an Martin Ender (-11 Bytes)

J42161217
quelle
Casesstellt sich als kürzer als Select(-4 Bytes) heraus: Tr[1^Union@Cases[FactorInteger@#,_?PrimeQ,2]]&(besteht alle Testfälle auf einem frischen Kernel)
JungHwan Min
Wie wäre es Count[Union@@FactorInteger@#,_?PrimeQ]&? (Habe nicht alle Testfälle überprüft.)
Martin Ender
@ MartinEnder scheint, als sollte es funktionieren. Besteht auch alle Testfälle.
JungHwan Min
5

05AB1E , 9 7 Bytes

2 Bytes dank Kevin Cruijssen gespeichert

ÓsfìÙpO

Probieren Sie es online aus!

Erläuterung

Ó        # 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
quelle
1
-1 Byte durch Verwendung €pOnach dem Zusammenführen der Primfaktoren und Exponenten:ÓsfìÙ€pO
Kevin Cruijssen
@ KevinCruijssen: Danke! Speichert tatsächlich 2, da nicht benötigt wird.
Emigna
Ah, natürlich ... Wow, ich bin mir nicht sicher, wie ich das verpasst habe, haha ​​xD
Kevin Cruijssen
4

Gelee ,  9  7 Bytes

ÆFFQÆPS

Probieren Sie es online aus! oder Schauen Sie sich die Testsuite an.

Wie?

ÆFFQÆPS ~ Vollständiges Programm.

ÆF ~ Primfaktorisierung als [Primzahl, Exponent] -Paare.
  F ~ Abflachen.
   Q ~ Deduplizieren.
    ÆP ~ Überprüfen Sie für jeden, ob es sich um eine Primzahl handelt. 1 wenn wahr, 0 wenn falsch.
      S ~ Summe.
Mr. Xcoder
quelle
4

Gaia , 6 Bytes

ḋ_uṗ¦Σ

Probieren Sie es online aus!


  • berechnet die Primfaktorisierung als [Primzahl, Exponent] -Paare.

  • _ glättet die Liste.

  • u Entfernt doppelte Elemente.

  • ṗ¦ordnet die Elemente zu und gibt 1 zurück, wenn eine Primzahl gefunden wird, andernfalls 0 .

  • Σ summiert die Liste.

Mr. Xcoder
quelle
3

CJam (13 Bytes)

{mFe__&:mp1b}

Online-Testsuite

Dies ist ziemlich einfach: Primzahlen mit Multiplizitäten erhalten, auf bestimmte Werte reduzieren, Primzahlen filtern, zählen.

Leider wies Martin auf einige Fälle hin, die in meiner ursprünglichen Antwort nicht durch den leicht interessanten Trick behandelt wurden, obwohl er auch eine 1-Byte-Einsparung lieferte, indem er beobachtete, dass da mpgibt 0oder 1es eher abgebildet als gefiltert werden kann.

Peter Taylor
quelle
1

Eigentlich 7 Bytes

w♂i╔♂pΣ

Probieren Sie es online aus!

Erläuterung:

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
quelle
1

Brachylog , 7 Bytes

ḋọcdṗˢl

Probieren Sie es online aus!

           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.

Eine lustige 9-Byte-Version: ḋọ{∋∋ṗ}ᶜ¹

Nicht verwandte Zeichenfolge
quelle
0

R + Zahlen, 92 Bytes

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

Probieren Sie es online aus!

Giuseppe
quelle
0

J, 20 Bytes

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

Von Hand gezählt lol, also sag mir, ob das aus ist.

Irgendwelche Golfvorschläge?

Langweilige Übermittlung: Reduzieren Sie die Primfaktorisierungstabelle und zählen Sie die Primzahlen.

cole
quelle
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
quelle