Jednym ze sposobów przedstawienia liczby naturalnej jest pomnożenie wykładników liczb pierwszych. Na przykład 6 może być reprezentowane przez 2 ^ 1 * 3 ^ 1, a 50 może być reprezentowane przez 2 ^ 1 * 5 ^ 2 (gdzie ^ oznacza eksponencję). Liczba liczb pierwszych w tej reprezentacji może pomóc ustalić, czy użycie tej metody reprezentacji jest krótsze w porównaniu z innymi metodami. Ale ponieważ nie chcę ich obliczać ręcznie, potrzebuję programu, który to dla mnie zrobi. Ponieważ jednak muszę pamiętać program, dopóki nie wrócę do domu, musi on być jak najkrótszy.

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 przedstawienia danych wejściowych, zgodnie z opisem we wstępie.

Przypadki testowe:

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)

To jest OEIS A001221 .

Punktacja:

To jest golf golfowy , najniższy wynik w bajtach wygrywa!

MATL , 4 3 bajty

-1 bajt dzięki Luis Mendo

YFz

Wypróbuj online!

YF         Exponents of prime factors
  z        Number of nonzeros

Oryginalna odpowiedź:

Yfun

Wypróbuj online!

Ver Yfunodpowiedź.

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

05AB1E , 2 bajty

^{kolejna dość nudna odpowiedź ...}

fg

Pełny program akceptujący wprowadzanie numeryczne i drukujący wynik

Wypróbuj online!

W jaki sposób?

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

Mathematica, 7 bajtów

PrimeNu

Tak, jest wbudowany.

Mathematica, 21 bajtów

Length@*FactorInteger

Długa droga dookoła.

Gaia , 2 bajty

^{Jeszcze jedna nudna odpowiedź ... --- J. Allan}

ḋl

Wypróbuj online!

• ḋ- Rozkład na czynniki pierwsze jako pary [liczba pierwsza, wykładnik] .

• l - długość

Python 2, 56 bajtów

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 bajtów

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

Dane wejściowe są jednostkowe.

Dzięki @MartinEnder za grę w golfa 1 bajt!

Wypróbuj online!(obejmuje konwerter dziesiętny na unarny)

Jak to działa

Ponieważ program składa się z jednego wyrażenia regularnego z &modyfikatorem, Retina po prostu liczy liczbę nakładających się dopasowań. Zakłada się, że dane wejściowe składają się z n powtórzeń 1 i nic więcej.

Negatywne spojrzenie w przyszłość

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

dopasowania w miejscach między 1 , po których nie występują dwa lub więcej 1 ( 11+), po których następuje jedno lub więcej powtórzeń o tej samej ilości 1 ( \1+), a następnie koniec wprowadzania ( $).

Dowolna liczba kompozytu AB z a, b> 1 może być zapisana jako b powtórzeń a powtórzeń 1 , tak uprzedzona pasuje tylko miejsca następnie p powtórzeń 1 , gdzie p = 1 lub p jest liczbą pierwszą.

Wyrażenie regularne

(11+)$

upewnia się, że p> 1 , wymagając co najmniej dwóch 1 's ( 11+) i przechowuje ogon 1 ' w drugiej grupie przechwytywania ( \2).

Wreszcie pozytywny wygląd

(?<=^\2+)

sprawdza, czy całe dane wejściowe składają się z wystąpień kp ( k ≥ 1 ) z 1 , sprawdzając, czy p dzieli dane wejściowe.

Zatem każde dopasowanie odpowiada unikalnemu dzielnikowi głównemu p .

Narzędzia Bash + GNU, 33

• 1 bajt zapisany dzięki @Dennis

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

Wypróbuj online .

Wyjaśnienie

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

Galaretka , 3 bajty

^{dość nudna odpowiedź ...}

ÆFL

Monadyczny link pobierający numer i zwracający numer

Wypróbuj online!

W jaki sposób?

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

Ohm v2 , 2 bajty

ml

Wypróbuj online!

Dwa wbudowane elementy znajdują się obok siebie w dokumentacji lol.

Galaretka , 2 bajty

^{Jeszcze jedna nudna odpowiedź ... --- J. Allan}

Æv

Wypróbuj online!

Wbudowany.

Alice , 10 bajtów

/o
\i@/Dcd

Wypróbuj online!

Wyjaśnienie

/o
\i@/...

To tylko standardowa platforma dla liniowych programów obciążonych arytmetyką, które wymagają dziesiętnych operacji we / wy. Właściwy program jest wtedy po prostu:

Dcd

Co robi:

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 bajtów

* W przypadku @SEJPM poproś o wyjaśnienie: to, co tutaj robię, to od 2 - n (które się zmieni, i ostatecznie będzie największym czynnikiem podstawowym) - teraz, jeśli bieżąca liczba dzieli, chcę ją policzyć tylko raz (nawet chociaż może to być współczynnik 2 * 2 * 2 * 3 - 2 jest liczone raz) - więc na obraz pojawia się „j”, gdy j nie jest określone w wywołaniu funcion - j otrzyma wartość „ undefined ", a gdy n% i == 0, wtedy wywołuję funkcję z j = 1 w następnym wywołaniu) - a następnie dodaję tylko 1, gdy j jest niezdefiniowany, co jest! j + Funkcja (n / i, i, ( j = 1 lub tylko 1)). nie zmieniam i w tej kwestii, ponieważ może nadal być podzielne przez i ponownie (2 * 2 * 3), ale wtedy j będzie równe 1 i nie będzie się liczyło jako czynnik. mam nadzieję, że wyjaśniłem to wystarczająco dobrze.

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

jeśli ostatnia liczba pierwsza jest bardzo duża, to będzie miała maksymalny stos wywołań - jeśli jest to problem, mogę zrobić iteracyjny

CJam , 7 5 bajtów

Dzięki Martin Ender za 2 bajty!

{mF,}

Blok anonimowy (funkcja), który oczekuje numeru wejściowego na stosie i zastępuje go numerem wyjściowym.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

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

Brachylog , 3 bajty

ḋdl

Wypróbuj online!

Wyjaśnienie

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