Moc pierwsza jest dodatnią liczbą całkowitą n, którą można zapisać w postaci n = p k, gdzie p jest liczbą pierwszą, a k jest liczbą całkowitą dodatnią. Na przykład niektóre główne moce są [2, 3, 5, 4, 9, 25, 8, 27, 125]
.
Następnie rozważmy podstawowe potęgi 2. Są [2, 4, 8, 16, ...]
i mogą być zapisane w formie 2 k . Wszystkie zostaną uwzględnione przy rozważaniu mocy pierwszych poniżej 20. Jednak 16 to maksymalna moc pierwotna z podstawową liczbą pierwszą 2 w tym zakresie. Moc pierwotna p k jest maksymalna w zakresie, jeśli jest to najwyższa moc p w tym zakresie. Interesuje nas tylko maksymalna moc pierwotna w każdym zakresie, więc należy wykluczyć wszystkie niższe moce podstawowe.
Twoim celem jest napisanie funkcji lub programu, który przyjmuje dodatnią liczbę całkowitą n i wyprowadza maksymalne liczby pierwsze w zakresie [2, 3, 4, ..., n]
.
Podziękowania dla @ Peter Taylor za wyjaśnienie definicji maksymalnej mocy pierwotnej i nie tylko.
Zasady
- To jest golf golfowy, więc ustaw swój kod tak krótko, jak to możliwe.
- Te maksymalne prime uprawnienia mogą być wyprowadzane w dowolnej kolejności, ale nie może być żadnych duplikatów.
Przypadki testowe
n result
1 []
2 [2]
3 [2, 3]
4 [3, 4]
5 [3, 4, 5]
6 [3, 4, 5]
7 [3, 4, 5, 7]
20 [5, 7, 9, 11, 13, 16, 17, 19]
50 [11, 13, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49]
100 [11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97]
10000 <1229 results>
[101, 103, 107, 109, 113, 127, 131, 137, 139, 149, ..., 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]
Pełną listę maksymalnych mocy pierwszych dla 10000 można znaleźć tutaj .
Power floor
Co do choleryMathematica,
444340 bajtówZaoszczędzone 4 bajty dzięki mile i Martinowi Enderowi
n#^⌊#~Log~n⌋&/@Select[Range@n,PrimeQ]
⌊
i⌋
są3
znakami bajtowymiU+230A
i odpowiednioU+230B
reprezentującymi\[LeftFloor]
i\[RightFloor]
.Wyjaśnienie:
Czysta funkcja.
#
jest skrótem odSlot[1]
którego reprezentuje pierwszy argument doFunction
.PrimePi@#
Liczy liczbę liczb pierwszych mniejszych lub równych#
,Range@PrimePi@#
jest listą pierwszychPrimePi[#]
liczb całkowitych dodatnich, podobniePrime@Range@PrimePi@#
jak lista liczb pierwszych mniejszych lub równych#
(jest to jeden bajt krótszy niżSelect[Range@#,PrimeQ]
). Symbolx
jestSet
równy tej liście, a następnie podnoszony doPower
⌊x~Log~#⌋
, który jest listąFloor[Log[n,#]]
dla każdegon
wx
. W Mathematica podniesienie listy doPower
innej listy o tej samej długości powoduje wyświetlenie listy mocy odpowiadających jej elementów.źródło
Range@#~Select~PrimeQ
będzie krótszy niżPrime@Range@PrimePi@#
... ale to remisTreeForm
MATL, 13 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
Galaretka , 8 bajtów
Wypróbuj online!
Jak to działa
źródło
Galaretka ,
129 bajtówWypróbuj online! (metoda jest zbyt wolna dla przypadku 10000).
W jaki sposób?
Tworzy listę p k w kolejności p .
źródło
Pyth, 13 bajtów
Wypróbuj tutaj!
Od jakiegoś czasu nie grałem w Pyth, więc wszelkie wskazówki dotyczące golfa są mile widziane.
źródło
Nie mogłem znaleźć krótszego rozwiązania Mathematica niż rozwiązania ngenisis , ale pomyślałem, że zaproponuję kilka (mam nadzieję, że interesujących) alternatywnych podejść.
Mathematica, 65 bajtów
Najpierw
{#,#}&/@Range@#~Select~PrimeQ
budujemy listę wszystkich liczb pierwszych w odpowiednim zakresie, ale z uporządkowanymi parami każdej liczby pierwszej, na przykład{ {2,2}, {3,3}, ...}
. Następnie operujemy na tej liście wielokrotnie z regułą zastępowania{a_,b_}/;a<=#:>{b a,b}
, która zwielokrotnia pierwszy element uporządkowanej pary przez drugi, aż pierwszy element przekroczy wejście. Następnie stosujemy#/#2&@@@
do wyjścia, dla każdej uporządkowanej pary, pierwszy element podzielony przez drugi. (W końcu posortowane są według liczby pierwszej: przykładowy wynik to{16, 9, 5, 7, 11, 13, 17, 19}
.)Mathematica, 44 bajty
Funkcja von Mangoldta
Λ(n)
jest interesującą funkcją teorii liczb: jest równa 0, chyba żen
jest siłą pierwszą p k , w którym to przypadku jest równalog p
(nielog n
). (Są to dzienniki naturalne, ale to nie ma znaczenia.) W ten sposóbMangoldtLambda@#->#&~Array~#
tworzy tablicę reguł,{ 0->1, Log[2]->2, Log[3]->3, Log[2]->4, Log[5]->5, 0->6, ... }
których długość jest liczbą całkowitą wejściową.Następnie przekształcamy tę listę reguł w „skojarzenie” za pomocą
<|...|>
. Skutkuje to zachowaniem tylko ostatniej reguły z dowolną wartością po lewej stronie. Innymi słowy, to wyrzucićLog[2]->2
iLog[2]->4
iLog[2]->8
i zachować tylkoLog[2]->16
(przy założeniu, że wejście jest między 16 i 31 w tym przykładzie). Dlatego jedynymi pozostałymi prawymi stronami są maksymalne moce pierwotne - z wyjątkiem jednej pozostałej reguły0->n
, gdzien
jest największa moc niepierwotna aż do wejściowej liczby całkowitej. AleRest
odrzuca to, co niepożądane, rządzi iValues
wyciąga prawą stronę z reguł w stowarzyszeniu. (W końcu posortowano jak wyżej.)Nieco dłuższa (46 bajtów) wersja, która zlicza liczbę wystąpień każdego z nich,
log p
a następnie potęguje się, aby przekonwertować do maksymalnych liczb pierwszych:źródło
CJam ,
2120 bajtówZaoszczędzono 1 bajt dzięki Martinowi Enderowi
Wypróbuj online!
Wyjaśnienie
źródło
Brachylog , 15 bajtów
Wypróbuj online!
To daje moc od największej do najmniejszej.
To jest bardzo nieefektywne.
Wyjaśnienie
Najpierw znajdzie to największy rozkład liczb pierwszych dla każdej liczby pierwszej, ze względu na sposób
⊇
działania: od lewej do prawej i od największych do najmniejszych podzbiorów.źródło
Brachylog ,
242119 bajtów3 + 2 bajty zapisane dzięki Fatalize!
Po raz pierwszy korzystam z Brachylog i wiem, że niektóre rzeczy można było zrobić na krótsze sposoby, ale cieszę się, że to nawet działa: D
Wypróbuj online! (Zwracane wartości są uporządkowane według podstawowych liczb pierwszych)
Wyjaśnienie:
źródło
?
oraz.
dla danych wejściowych i wyjściowych zamiastI
iX
jako takie:{≥N~^.hṗ:N×>?∧0<~t}ᶠ^ᵐ
0<~t
i stwierdzając, że każdy element Wyjścia.
jestℕ₁ = [1, ..., +inf)
taki:{≥N~^.ℕ₁ᵐhṗ:N×>?∧}ᶠ^ᵐ
{≥.~^ℕ₁ᵐhṗ:.×>?∧}ᶠ
(używanie N bezpośrednio jako danych wyjściowych) nie działa? Najpierw spróbowałem czegoś takiego, ale potem musiałem użyć X i zastosować ^{...}ᶠ
którym powoduje dziwne zachowanie. Zamierzam to zmienić i przyjrzę się konkretnie, dlaczego ten program nie działa tak samo jak powyższy.{≥.~^ℕ₁ᵐhṗ:.≜×>?∧}ᶠ
sposób : W ten sposób uzyskasz prawidłową etykietę. (W międzyczasie wprowadzono zmiany w specyfikacjach, ale tak naprawdę nie zmieniają one zachowania tego konkretnego programu, więc nie wyklucza jego konkurowania). Oszczędza to 2 bajty05AB1E ,
1512 bajtówWypróbuj online!
Wyjaśnienie
źródło
Narzędzia Bash + GNU, 74 bajty
Wypróbuj online!
Numer wejściowy jest przekazywany jako argument. Dane wyjściowe są drukowane na standardowym wyjściu. (Jak zwykle, stderr jest ignorowany).
Przykładowe dane wyjściowe:
Oto jak to działa:
Wywołaj argument N.
seq
generuje wszystkie liczby od 1 do N ifactor
uwzględnia je wszystkie.Wyrażenie regularne w wywołaniu sed identyfikuje te linie, w których liczba jest liczbą pierwszą P, i zastępuje te linie liniami o postaci `
(gdzie P i N są zastępowane ich rzeczywistymi wartościami liczbowymi, a wszystko inne jest kopiowane dosłownie, nawet cudzysłowy i średniki oraz ciąg znaków
print
).Linie te są podawane jako dane wejściowe
bc -l
; bc drukuje wartości trzech wskazanych liczb, po których następuje nowa linia, a następnie drukuje znaki/^p
. (W bc, l (x) oznacza logarytm naturalny z x.) JK KCiągi drukowane przez bc są następnie podawane jako dane wejściowe do dc; dc wypisuje wartość każdego P ^ (log (N) / log (P)) przy użyciu arytmetyki liczb całkowitych (obcinanie); to największa moc P, która wynosi <= N.
Jedną rzeczą, która jest powyżej, jest to, co dzieje się z liniami wytwarzanymi przez czynniki, które nie odpowiadają liczbom pierwszym. Te wiersze nie pasują do wyrażenia regularnego w wywołaniu sed, więc nie są zastępowane. W rezultacie linie te zaczynają się od liczby, po której następuje dwukropek, który generuje błąd, gdy jest podawany jako dane wejściowe
bc
. Ale bc po prostu drukuje do stderr, co ignorujemy; nie drukuje niczego na standardowe wyjście. Domyślnie stderr jest ignorowany w PPCG .źródło
Haskell ,
73 6766 bajtówWypróbuj online! Stosowanie:
Edycja: 6 bajtów off dzięki Zgarb!
Wyjaśnienie:
źródło
last[x^i|i<-[1..n],x^i<=n]
.Galaretka , 9 bajtów
Jeden bajt dłuższy niż moja inna odpowiedź , ale kończy się na wejściu 10.000 to kilka sekund.
Wypróbuj online!
Jak to działa
źródło
JavaScript (ES6),
118120119114112105 bajtówSugestie mile widziane. Jest to dość długie, ale wydawało się, że warto opublikować, ponieważ wykonuje wszystkie testy podzielności jawnie, zamiast używać wbudowanych funkcji liczb pierwszych.
Uwagi:
źródło
Szałwia, 43 bajty
Mapuje każdą liczbę pierwszą w zakresie
primes(i)
do maksymalnej mocy pierwszej.ln
jest tylko aliasem,log
więc akceptuje alternatywne zasady, chociaż jego nazwa sugeruje, że można używać tylko zasade
.źródło
primes
funkcję i naprawdę się podnieciłem. Nigdy więcej nie ufaj przepełnieniu stosu.Haskell,
11090 bajtów- zaktualizowano według opinii Laikoni
źródło
Exception: Prelude.last: empty list
zaf 2
if 3
.f 4
powraca[2,3]
zamiast[4,3]
, myślę, żetakeWhile(<n)
musisztakeWhile(<=n)
. Jednak użyciefst.span
zamiasttakeWhile
jest o jeden bajt krótsze.Haskell , 70 bajtów
Definiuje funkcję
f
. Wypróbuj online!Wyjaśnienie
Chodzi o to, aby przefiltrować zakres
[2..n]
dla tych liczb,k
które spełniająk == p^length(divisors k)
ip*k > n
, gdziep
jest najmniejszy główny dzielnikk
.źródło
PHP,
101939188 bajtówtylko trochę prawdziwych matematyki ...
awaria
źródło
JavaScript ES7, 93 bajty
Rekurencyjnie iteruj
i
od 0 do włącznien
. Jeślii
jest liczbą pierwszą, podnieś ją do najwyższego wykładniczego wykładnika, który sprawia, że<= n
(i ^ floor(log(n) / log(i))
)źródło