Najwięksi pierwsi wykładnicy

22

Biorąc pod uwagę liczbę całkowitą n >= 2, wyprowadzaj największy wykładnik w jego pierwotnym rozkładzie na czynniki pierwsze. Jest to sekwencja OEIS A051903 .

Przykład

Let n = 144. Jego podstawową faktoryzacją jest 2^4 * 3^2. Największy wykładnik to 4.

Przypadki testowe

2 -> 1
3 -> 1
4 -> 2
5 -> 1
6 -> 1
7 -> 1
8 -> 3
9 -> 2
10 -> 1
11 -> 1
12 -> 2
144 -> 4
200 -> 3
500 -> 3
1024 -> 10
3257832488 -> 3
code-golf  number-theory  primes  integer  factoring 
— Mego
źródło
— Mego

Odpowiedzi:

4

Python 2 , 78 bajtów

n=input()
e=m=0
f=2
while~-n:q=n%f<1;f+=1-q;e=q*-~e;m=max(m,e);n/=f**q
print m

Wypróbuj online!

-5 dzięki ovs .

Ta odpowiedź nie wykonuje kontroli wstępnych. Zamiast tego wykorzystuje fakt, że najwyższy wykładnik czynnika pierwszego będzie większy lub równy wykładnikowi dowolnego innego czynnika w dowolnej faktoryzacji liczby.

— Erik the Outgolfer
źródło
— ovs
Dzięki @ovs, przegapiłem to, gdy próbowałem szybko
— pisać
— ovs
@ovs wreszcie się rozluźnił od if / else, dzięki
— Erik the Outgolfer
4

Japt -h , 9 7 bajtów

k ü mÊn

Spróbuj

k ü mÊn     :Implicit input of integer
k           :Prime factors
  ü         :Group by value
    m       :Map
     Ê      :  Length
      n     :Sort
            :Implicit output of last element
— Kudłaty
źródło
2
— Wydaje
Dlaczego warto używać „ü: Grupuj według wartości” zamiast funkcji sortowania? Tak, być może dlatego, że sort zwraca jedną tablicę, ale potrzebujemy jednej tablicy tablic ...
— RosLuP
1
@RosLuP, Dokładnie; ütworzy tablice podrzędne o równych wartościach. To działa również sortować według wartości pierwszy, ale to nie jest istotne tutaj.
— Kudłaty
2

JavaScript 54 bajty

* zakładając nieskończony stos (tak jak w przypadku golfowych wyzwań)

P=(n,i=2,k)=>i>n?k:n%i?k>(K=P(n,i+1))?k:K:P(n/i,i,-~k)

console.log(P(2 )== 1)
console.log(P(3 )== 1)
console.log(P(4 )== 2)
console.log(P(5 )== 1)
console.log(P(6 )== 1)
console.log(P(7 )== 1)
console.log(P(8 )== 3)
console.log(P(9 )== 2)
console.log(P(10 )== 1)
console.log(P(11 )== 1)
console.log(P(12 )== 2)
console.log(P(144 )== 4)
console.log(P(200 )== 3)
console.log(P(500 )== 3)
console.log(P(1024 )== 10)
//console.log(P(3257832488 )== 3)
Rozwiń fragment kodu

— DanielIndie
źródło
2

Oktawa , 25 bajtów

@(n)[~,m]=mode(factor(n))

Wypróbuj online!

Wyjaśnienie

factorprodukuje tablicę (ewentualnie powtarzane) prime wykładniki Drugie wyjście modedaje liczbę razy, że pojawi się tryb (czyli najbardziej powtórzony wpis).

— Luis Mendo
źródło
1

Gaia , 4 bajty

ḋ)⌠)

Wypróbuj online!

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

    • ⌠ - Odwzoruj i zbierz wynik o maksymalnej wartości.

    • ) - Ostatni element (wykładnik).

    • ) - Ostatni element (maksymalny wykładnik)

Gaia , 4 bajty

ḋ)¦⌉

Wypróbuj online!

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

    • )¦ - Mapa z ostatnim elementem (wykładnikiem).

    • ⌉ - Pobiera maksymalny element.

— Pan Xcoder
źródło
1

Oktawa : 30 bajtów

@(x)max(histc(a=factor(x),a));
  1. a=factor(x)zwraca wektor zawierający czynniki pierwsze z x. Jest to wektor posortowany w porządku rosnącym, w którym pomnożenie wszystkich liczb factor(x)daje wynik xtaki, że każda liczba w wektorze jest liczbą pierwszą.
  2. histc(...,a)oblicza histogram na wektorze czynników głównych, gdzie przedziały są czynnikami głównymi. Histogram zlicza, ile razy widzieliśmy każdą liczbę pierwszą, uzyskując wykładnik każdej liczby pierwszej. Możemy tu trochę oszukiwać, ponieważ choć factor(x)zwrócą zduplikowane liczby lub pojemniki, tylko jeden z pojemników zarejestruje całkowitą liczbę wyświetleń liczby pierwszej.
  3. max(...) w ten sposób zwraca największy wykładnik.

Wypróbuj online!

— rayryeng - Przywróć Monikę
źródło
1

Alice , 17 bajtów

/o
\i@/w].D:.t$Kq

Wypróbuj online!

Wyjaśnienie

/o
\i@/...

Jest to tylko struktura dla prostych programów arytmetycznych z dziesiętnym We / Wy. Jest ...to rzeczywisty program, który ma już dane wejściowe na stosie i pozostawia dane wyjściowe na górze stosu.

Alice faktycznie ma wbudowane funkcje, aby uzyskać pierwszą faktoryzację liczby całkowitej (nawet z parami liczba pierwsza-wykładnik), ale najkrótszy, jaki wymyśliłem, używając ich jest o 10 bajtów dłuższy.

Zamiast tego chodzi o to, że wielokrotnie dzielimy jedną kopię każdego odrębnego czynnika pierwszego z danych wejściowych, aż osiągniemy 1 . Liczba kroków, jakie podejmuje, jest równa największemu pierwszemu wykładnikowi. Będziemy nadużywać głowicy taśmy jako zmiennej licznika.

w      Remember the current IP position. Effectively starts a loop.
  ]      Move the tape head to the right, which increments our counter.
  .D     Duplicate the current value, and deduplicate its prime factors.
         That means, we'll get a number which is the product of the value's
         unique prime factors. For example 144 = 2^4 * 3^2 would become
         6 = 2 * 3.
  :      Divide the value by its deduplicated version, which decrements the
         exponents of its prime factors.
  .t     Duplicate the result and decrement it. This value becomes 0 once we
         reach a result of 1, which is when we want to terminate the loop.
$K     Jump back to the beginning of the loop if the previous value wasn't 0.
q      Retrieve the tape head's position, i.e. the number of steps we've taken
       through the above loop.
— Martin Ender
źródło
1

Julia, 60 52 40 bajtów

f(x)=maximum(collect(values(factor(x))))

-12 + korekta dzięki Steadybox

— EricShermanCS
źródło
1
Myślę, że musisz dodać połączenie print(). Ponadto nie udało mi się uruchomić kodu w TIO w takiej postaci, w jakiej jest, zakładam, że działa on na innej wersji języka, która nie jest tam dostępna? Działa to dobrze w TIO: print(maximum(collect(values(factor(parse(BigInt,readline()))))))
— Steadybox
Działa to na tłumaczu (przynajmniej na moim komputerze). Powoduje również ostrzeżenie, ponieważ inicjowanie takiego BigInt zostało wycofane. Niemniej jednak, jeśli skopiujesz i wkleisz kod w obecnej postaci do interpretera Julii, powinien on działać. (jeśli wydruk jest wymagany, ponieważ musi być wyraźnie wydrukowany, źle to umieszczam)
— EricShermanCS
1
Jest print()to konieczne, ponieważ odpowiedź musi być pełnym programem (wyświetlającym dane wyjściowe) lub funkcją (zwracającą dane wyjściowe). W przeciwnym razie twoje rozwiązanie będzie w porządku. Wygląda na to, że możesz zapisać niektóre bajty (i uniknąć wydruku) w ten sposób:f(x)=maximum(collect(values(factor(x))))
— Steadybox
1
Nie ma za co! Oto meta post na temat dozwolonego formatu rozwiązania.
— Steadybox
0

Właściwie 4 bajty

w♂NM

Wypróbuj online!

w♂NM - Pełny program.

w - Przesuwa rozkład na czynniki pierwsze jako pary [liczba pierwsza, wykładnik].
 ♂N - Uzyskaj ostatni element każdego (wykładników).
   M - maksymalna.
— Pan Xcoder
źródło
Dokładnie tego rozwiązania użyłem do napisania przypadków testowych :)
— Mego
@Mego Czy uważasz, że może być krótszy (nie chcę, żebyś się zepsuł, jeśli masz krótszy, tylko pytam)? :)
— Mr. Xcoder,
Nie, uważam, że jest to optymalne w rzeczywistości.
— Mego
0

Python 2 , 64 bajty

-4 bajty dzięki H.PWiz.

lambda n:max(a*(n%k**a<1)for a in range(n)for k in range(2,-~n))

Wypróbuj online!

Port odpowiedzi Haskella H.PWiza . Udostępniam to tylko dlatego, że jestem dumny, że mogłem zrozumieć ten fragment kodu Haskell i go przetłumaczyć. : P

— całkowicie ludzki
źródło
Nie range(1,n)działa?
— H.PWiz
range(1, n)produkuje wszystkie liczby całkowite w [1, n).
— całkowicieludzki
1
Ach, cóż, właściwie nie musisz iść aż do n dlaa
— H.PWiz
Och, okej, nie do końca rozumiem matematykę. : P Dzięki!
— całkowicieludzki
1
— H.PWiz
0

Aksjomat, 61 bajtów

f n==(a:=factors n;reduce(max,[a.i.exponent for i in 1..#a]))

Po raz pierwszy stwierdzam, że możliwe jest zdefiniowanie funkcji bez użycia nawiasu (). Zamiast „f (n) ==” „fn ==” jeden znak mniej ...

— RosLuP
źródło
0

Rakieta , 83 79 bajtów

(λ(n)(cadr(argmax cadr((let()(local-require math/number-theory)factorize)n))))

Wypróbuj online!

(Nie jestem pewien, czy istnieje konsensus co do tego, co stanowi kompletne rozwiązanie Racket, więc idę z konwencją Mathematica, że ​​liczy się czysta funkcja).

Jak to działa

factorizedaje faktoryzację jako listę par: (factorize 108)daje '((2 2) (3 3)). Drugi element pary podaje cadrskrót, składający się z car(nagłówek listy) z cdr(ogon listy).

Głupio robię, (cadr (argmax cadr list))aby znaleźć maksimum drugich elementów, ale maxnie działa na listach: (max (map cadr list))nie robi tego, co chcemy. Nie jestem ekspertem od rakiet, więc może istnieje standardowy lepszy sposób na zrobienie tego.

Rakieta, 93 bajty

(λ(n)(define(p d m)(if(=(gcd m d)d)(+(p d(/ m d))1)0))(p(argmax(λ(d)(p d n))(range 2 n))n))

Wypróbuj online!

Jak to działa

Alternatywna wersja, która nie importuje, factorizea zamiast tego robi wszystko od zera, mniej więcej. Funkcja (p m d)wyszukuje najwyższą moc d, która dzieli m, a potem po prostu znaleźć najwyższą wartość (p n d)dla dpomiędzy 2i n. (Nie musimy ograniczać tego do liczb pierwszych, ponieważ nie będzie złożonej mocy, która działałaby lepiej niż moce podstawowe).

— Misza Ławrow
źródło
Myślę, że standardowe maxrozwiązanie jest, (apply max (map cadr list)ale (cadr (argmax cadr list))niestety krótsze.
— Misza Ławrow
0

APL (NARS), 15 znaków, 30 bajtów

{⌈/+/¨v∘=¨v←π⍵}

test:

  f←{⌈/+/¨v∘=¨v←π⍵}
  f¨2..12
1 1 2 1 1 1 3 2 1 1 2 
  f¨144 200 500 1024 3257832488
4 3 3 10 3

komentarz:

{⌈/+/¨v∘=¨v←π⍵}
          v←π⍵    π12 return 2 2 3; assign to v the array of prime divisors of argument ⍵
      v∘=¨        for each element of v, build one binary array, show with 1 where are in v array, else puts 0 
                  return one big array I call B, where each element is the binary array above
   +/¨            sum each binary element array of  B
 ⌈/               get the max of all element of B (that should be the max exponet)
— RosLuP
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.