Liczby pierwsze w rozkładzie na czynniki pierwsze

9

Widziałem kolejne główne wyzwanie w PPCG i bardzo mi się podobają. Potem źle przeczytałem tekst wprowadzający i zastanawiałem się, co wymyślili tutaj twórczy mózg.

Okazuje się, że postawione pytanie było trywialne, ale zastanawiam się, czy to samo dotyczy pytania, które (źle) przeczytałem:


6 może być reprezentowane przez 2 ^ 1 * 3 ^ 1, a 50 może być reprezentowane przez 2 ^ 1 * 5 ^ 2 (gdzie ^ oznacza eksponencję).

Twoje zadanie:

Napisz program lub funkcję, aby określić, ile różnych liczb pierwszych znajduje się w tej reprezentacji liczby.

Wejście:

Liczba całkowita n taka, że ​​1 <n <10 ^ 12, przyjęta dowolną normalną metodą.

Wynik:

Liczba różnych liczb pierwszych wymaganych do reprezentowania unikalnych czynników pierwszych n.

Przypadki testowe:

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)

To nie jest sekwencja OEIS.

Punktacja:

To jest , najniższy wynik w bajtach wygrywa!

pbeentje
źródło
Jaki jest oczekiwany wynik 64? Czy to 2 (2,3)(jako 6 można przedstawić jako 2 * 3) czy 1 (2)(zignorować 6)?
Emigna
dla 64oczekiwanego wyniku wynosi 1 (2). Podoba mi się pomysł robienia tego rekurencyjnie, ale nie w ten sposób czytam oryginalne pytanie. Myślałem, że 8640to odpowiedni przypadek testowy, ale powinien być bardziej precyzyjny - dzięki.
pbeentje
Twierdzisz, że nie jest to sekwencja OEIS. Czy to nie A001221, wartości (małej) funkcji omega?
Gray Taylor,
A001221 jest podobny, ale zaczyna się rozbierać na warunkach 8 i 9 (tutaj 2, A001221 1) z powodu włączenia wykładnika jako liczby pierwszej w tym ćwiczeniu.
pbeentje 10.10.17
O, rozumiem. Zapisz rozkład na czynniki pierwsze, a następnie sprawdź, ile różnych liczb pierwszych napisałem (niezależnie od roli, jaką odegrały). Zastanawiam się, co się stanie, jeśli pójdziesz o krok dalej i uwzględnisz wykładnik ...
Gray Taylor

Odpowiedzi:

5

Mathematica, 39 bajtów

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

Wypróbuj online!

dzięki Martinowi Enderowi (-11 bajtów)

J42161217
źródło
Casesokazuje się być krótszy niż Select(-4 bajty): Tr[1^Union@Cases[FactorInteger@#,_?PrimeQ,2]]&(przekazuje wszystkie przypadki testowe na świeżym jądrze)
JungHwan Min
Jak o Count[Union@@FactorInteger@#,_?PrimeQ]&? (Nie sprawdziłem wszystkich przypadków testowych.)
Martin Ender,
@MartinEnder wydaje się, że powinien działać. Przechodzi również wszystkie przypadki testowe.
JungHwan Min
5

05AB1E , 9 7 bajtów

Zaoszczędzono 2 bajty dzięki Kevinowi Cruijssenowi

ÓsfìÙpO

Wypróbuj online!

Wyjaśnienie

Ó        # 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
źródło
1
-1 bajt przy użyciu €pOpo połączeniu czynników pierwszych i wykładników:ÓsfìÙ€pO
Kevin Cruijssen
@KevinCruijssen: Dzięki! Właściwie oszczędza 2, ponieważ nie jest potrzebny.
Emigna
Ach, oczywiście .. Wow, nie wiem, jak mi tego brakowało, haha ​​xD
Kevin Cruijssen
4

Galareta ,  9  7 bajtów

ÆFFQÆPS

Wypróbuj online! lub Sprawdź pakiet testowy.

W jaki sposób?

ÆFFQÆPS ~ Pełny program.

ÆF ~ Pierwotne faktoryzacja jako pary [liczba pierwsza, wykładnik].
  F ~ Spłaszcz.
   Q ~ deduplikacja.
    ÆP ~ Dla każdego sprawdź, czy jest to liczba pierwsza. 1 jeśli prawda, 0 jeśli fałsz.
      S ~ Sum.
Pan Xcoder
źródło
4

Gaia , 6 bajtów

ḋ_uṗ¦Σ

Wypróbuj online!


  • oblicza pierwszą faktoryzację jako pary [liczba pierwsza, wykładnik] .

  • _ spłaszcza listę.

  • u usuwa zduplikowane elementy.

  • ṗ¦odwzorowuje elementy i zwraca 1, jeśli zostanie znaleziona liczba pierwsza, 0 w przeciwnym razie.

  • Σ podsumowuje listę.

Pan Xcoder
źródło
3

CJam (13 bajtów)

{mFe__&:mp1b}

Zestaw testów online

Jest to dość proste: uzyskaj liczby pierwsze z wielokrotnościami, zredukuj do różnych wartości, filtruj liczby pierwsze, policz.

Niestety Martin wskazał na niektóre przypadki, które nie zostały rozwiązane przez dość interesującą sztuczkę w mojej oryginalnej odpowiedzi, chociaż zapewnił również 1-bajtową oszczędność, obserwując, że od czasu mpdaje 0lub 1można go zmapować, a nie filtrować.

Peter Taylor
źródło
2

Ohm v2 , 6 5 bajtów

-1 bajt dzięki @ Mr.Xcoder

ä{UpΣ

Wypróbuj online!

Cinaski
źródło
5 bajtów:ä{UpΣ
Pan Xcoder,
@ Mr.Xcoder Thanks! Szukałem tego wbudowanego, ale nie mogłem go znaleźć ...
Cinaski,
1

Właściwie 7 bajtów

w♂i╔♂pΣ

Wypróbuj online!

Wyjaśnienie:

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
źródło
1

Python 2 , 142 135 119 bajtów

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

Wypróbuj online!

ovs
źródło
1

Łuska ,  11  10 bajtów

#ṗuS+omLgp

Wypróbuj online!


EDYCJA: Zaoszczędził 1 bajt dzięki Zgarb .

Pan Xcoder
źródło
1
#ṗuS+omLgpzapisuje bajt.
Zgarb
1

Brachylog , 7 bajtów

ḋọcdṗˢl

Wypróbuj online!

           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.

Zabawna 9-bajtowa wersja: ḋọ{∋∋ṗ}ᶜ¹

Niepowiązany ciąg
źródło
0

R + liczby, 92 bajty

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

Wypróbuj online!

Giuseppe
źródło
0

J, 20 bajtów

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

Liczone ręcznie lol, więc powiedz mi, czy to jest wyłączone.

Wszelkie sugestie dotyczące gry w golfa?

Nudne poddanie: spłaszcz tabelę faktoryzacji liczb pierwszych i policz liczby pierwsze.

kapusta
źródło
0

JavaScript (ES6), 145 bajtów

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
źródło