Redivosite to słowo portmanteau wymyślone wyłącznie w tym celu. To połączenie redukcji, podziału i kompozytu.
Definicja
Biorąc pod uwagę liczbę całkowitą N> 6 :
- Jeśli N jest liczbą pierwszą, N nie jest liczbą ponownie złożoną.
- Jeśli N jest złożony:
- wielokrotnie obliczyć N '= N / d + d + 1, aż N' będzie liczbą pierwszą, gdzie d jest najmniejszym dzielnikiem N większym niż 1
- N jest liczbą ponownie złożoną wtedy i tylko wtedy, gdy końcowa wartość N ' jest dzielnikiem N
Poniżej znajduje się 100 pierwszych numerów Redivosite (brak wpisu OEIS w momencie publikacji):
14,42,44,49,66,70,143,153,168,169,176,195,204,260,287,294,322,350,414,462,518,553,572,575,592,629,651,702,726,735,775,806,850,869,889,891,913,950,1014,1023,1027,1071,1118,1173,1177,1197,1221,1235,1254,1260,1302,1364,1403,1430,1441,1554,1598,1610,1615,1628,1650,1673,1683,1687,1690,1703,1710,1736,1771,1840,1957,1974,2046,2067,2139,2196,2231,2254,2257,2288,2310,2318,2353,2392,2409,2432,2480,2522,2544,2635,2640,2650,2652,2684,2717,2758,2760,2784,2822,2835
Przykłady
- N = 13 : 13 jest liczbą pierwszą, więc 13 nie jest liczbą rediwersyjną
- N = 32 : 32/2 + 3 = 19; 19 nie jest dzielnikiem ani 32, więc 32 nie jest liczbą rediwersyjną
- N = 260 : 260/2 + 3 = 133, 133/7 + 8 = 27, 27/3 + 4 = 13; 13 jest dzielnikiem lub 260, więc 260 jest liczbą rediwersyjną
Twoje zadanie
- Biorąc pod uwagę liczbę całkowitą N , zwróć prawdziwą wartość, jeśli w przeciwnym razie jest to liczba redywidualna lub wartość fałszowania. (Możesz również wypisać dowolne dwie różne wartości, o ile są one spójne).
- Gwarantowane wejście jest większe niż 6 .
- To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach!
code-golf
decision-problem
integer
division
Arnauld
źródło
źródło
a(n)
bezpośrednio, albo ponieważ możesz obliczyć termin z poprzednich). Dzięki, Arnauld, za zmianę wyzwania. :)Odpowiedzi:
Haskell,
918583807574 bajtówWypróbuj online!
Edycja: -2 bajty dzięki @BMO, -3 bajty dzięki @ H.PWiz i
-5-6 bajtów dzięki @ Ørjan Johansenźródło
Łuska , 14 bajtów
Wypróbuj online!
-3 dzięki H.PWiz .
źródło
Ω
Γ
...Γ
podana lista [a, b, c ...] będzie miała zastosowanie~+→Π
doa
i[b,c...]
.~+→Π
dodajea+1
doproduct[b,c...]
.a
jest najmniejszym dzielnikiem,product[b,c...]
jestN/d
C (gcc) ,
9489 bajtówWypróbuj online!
Wyjaśnienie
źródło
Galaretka , 14 bajtów
Wypróbuj online!
Jak to działa
źródło
Python 2 ,
9791 bajtówWypróbuj online!
Dane wyjściowe za pośrednictwem kodu wyjścia.
Nie golfowany:
Wypróbuj online!
źródło
05AB1E ,
1716 bajtówWypróbuj online!
Wyjaśnienie
źródło
Pyth , 20 bajtów
Wypróbuj tutaj!
Jak to działa
Pierwsze 4 bajty (
<P_Q
) sprawdzają tylko, czy dane wejściowe nie są liczbą pierwszą.Z pomocą Emigny udało mi się zaoszczędzić 3 bajty.
źródło
head(P)
zamiastfiITZ2
części, ponieważ najmniejszy dzielnik większy niż 1 zawsze będzie liczbą pierwszą?Python 3 , 149 bajtów
Wypróbuj online!
Stosując podejście sitowe. Powinny być szybkie (
O(N log log N)
= złożoność czasowa sita Eratostenesa) nawet przy dużychN
(ale zapisujeO(N)
liczby całkowite w pamięci)Uwaga:
n
nie przekraczająN
, a zamiast tegoN > 7
p
można zastosowaćrange(2,N)
zamiastrange(2,N+1)
przesiewania./
nie działa,//
należy go użyć z powodu indeksu listy.range
w innej zmiennej niestety nie pomaga.Wyjaśnienie:
-~N
==N+1
.s
jest inicjowanaN+1
zerami (Python indeksuje 0, więc indeksy to0..N
)s[n]
oczekuje się,0
żen
będzie liczbą pierwszą, ap
dlap
liczby minimalnej, która dzieli,n
jeślin
jest liczbą złożoną.s[0]
as[1]
wartości nie są ważne.Dla każdego
p
w zakresie[2 .. N-1]
:s[p] < 1
(to znaczys[p] == 0
), top
jest liczbą pierwszą i dla każdego z nichq
jest wielokrotnościąp
is[q] == 0
, przypisujs[q] = p
.Ostatnie 2 wiersze są proste, z tym wyjątkiem, że
n//s[n]-~s[n]
==(n // s[n]) + s[n] + 1
.Python 3 , 118 bajtów
Wypróbuj online!
Kosztem nieco gorszej wydajności. (Ten działa w
O(N log N)
złożoności czasowej, przy założeniu rozsądnej implementacji wycinków Pythona)Odpowiednik pełnego programu wynosi 117 bajtów .
źródło
n//s[n]-~s[n]
zamiastn//s[n]+s[n]+1
149 bajtów.or p
może być|p
or p
wykonuje logiczne lub, podczas gdy|p
wykonuje bitowe lub. To znaczy,a or b
jestb if a == 0 else a
.for
aby użyć plasterka zamiast innegofor
.range
Jest odwrócony, więc niższe indeksy zastąpią te duże, i uruchomieniem plasterek na2*p
nie zastąpis[0]
lubs[p]
.Haskell , 110 bajtów
Wypróbuj online!
Niezbyt szczęśliwy ...
źródło
Oktawa , 92 bajty
Wypróbuj online!
źródło
APL (Dyalog) , 50 bajtów
Wypróbuj online!
źródło
Japt,
2524 bajtówObawiam się, że mogłem pójść w tym kierunku, ale zabrakło mi czasu na wypróbowanie innego podejścia.
Dane wyjściowe
0
dla false lub1
true.Spróbuj
źródło
Perl 5 , 291 + 1 (-a) = 292 bajtów
Darn Perl za to, że nie ma natywnego sprawdzania liczb pierwszych.
Wersja bez golfa,
Wypróbuj online!
źródło
Wolfram Language (Mathematica) , 64 bajty
Prosta implementacja za pomocą rekurencyjnego zastępowania wzorca
(zastąpienie „\ [Dzielenie]” symbolem „∣” pozwala zaoszczędzić 7 bajtów)
Wypróbuj online!
źródło
Czysty ,
128117114 bajtówWypróbuj online!
źródło
J , 35 bajtów
Wypróbuj online!
Minimalny dzielnik będący pierwszym czynnikiem podstawowym został skradziony z rozwiązania Jelly @ Dennisa (wcześniej używałem
<./@q:
).Powinien istnieć lepszy sposób na wykonanie iteracji, ale nie mogę tego znaleźć. Myślałem o tym, aby uniknąć wykonywania testu pierwotności (
^:(0&p:)
) i zamiast tego używać negatywnych, ale wygląda na to, że będzie to nieco dłużej, ponieważ będziesz potrzebować_2{
i kilku zmian, które mogą nie dać zmniejszenia netto.Naprawdę czuję, że musi istnieć sposób na uniknięcie parens wokół kontroli pierwotności.
Objaśnienie (rozwinięty)
źródło
APL NARS, 43 znaki, 85 bajtów
(mając nadzieję, że zbiegnie się dla wszystkich liczb> 6) test:
Pomysł użycia 2 anonimowych funkcji trafił do innego rozwiązania Apl.
źródło
Pyt , 44 bajty
Wyjaśnij poniższy kod - jedyne różnice to (1), że N jest wcześniej zmniejszany, aby uwzględnić przyrost na początku pętli, i (2) używa NOR zamiast OR.
Wypróbuj online!
Zrobiłem to, zanim ponownie przeczytałem pytanie i zauważyłem, że chciał tylko prawdy / fałszu.
Pyt, 52 bajty
Drukuje nieskończoną listę liczb Redivosite.
Wyjaśnienie:
Wypróbuj online!
źródło