Ze wszystkich lat, w których podejmowałem to wyzwanie, rok 2017 jest pierwszym rokiem, który był liczbą pierwszą. Pytanie dotyczy więc liczb pierwszych i ich właściwości.

Twoim zadaniem jest stworzenie programu lub funkcji, która weźmie dowolną dużą liczbę całkowitą dodatnią jako dane wejściowe i wyprowadzi lub zwróci, niezależnie od tego, czy liczba ma wartość 2,017 - to znaczy, czy największy czynnik pierwszy w tej liczbie wynosi 2,017 lub mniej.

Niektóre przykładowe dane wejściowe i ich wyniki:

1 (has no prime factors)
true

2 (= 2)
true

80 (= 2 x 2 x 2 x 2 x 5)
true

2017 (= 2017)
true

2019 (= 3 x 673)
true

2027 (= 2027)
false

11111 (= 41 x 271)
true

45183 (= 3 x 15061)
false

102349 (= 13 x 7873)
false

999999 (= 3 x 3 x 3 x 7 x 11 x 13 x 37)
true

1234567 (= 127 x 9721)
false

4068289 (= 2017 x 2017)
true

Twój program nie musi dosłownie wyprowadzać truei false- żadnych wartości zgodnych z prawdą lub fałszem, aw rzeczywistości dowolne dwa różne wyniki, które są spójne we wszystkich przypadkach prawdziwych i fałszywych, są w porządku.

Nie możesz jednak używać liczb pierwszych w kodzie źródłowym. Liczby pierwsze występują w dwóch rodzajach:

• Znaki lub sekwencje znaków reprezentujące literały liczb pierwszych.

  • Znaki 2, 3, 5, i 7są nielegalne w językach, w których numery są ważne tokeny.

  • Numer 141jest nielegalny, ponieważ zawiera 41, mimo że 1i 4jest w inny sposób ważny.

  • Znaki Bi D(lub bi d) są nielegalne w językach, w których są zwykle używane jako 11 i 13, takich jak CJam lub Befunge.

• Znaki, które mają wartości Unicode o największej wartości lub zawierają w swoich kodowaniach bajty o największej wartości.

  • Znaki %)+/5;=CGIOSYaegkmqsą nielegalne w ASCII, podobnie jak znak powrotu karetki.

  • Znak ójest nielegalny w UTF-8, ponieważ ma 0xb3w nim kodowanie . Jednak w ISO-8859-1 jego kodowanie jest proste 0xf3, które jest złożone i dlatego jest w porządku.

Wygrywa najkrótszy kod do wykonania powyższego w dowolnym języku.

Galaretka , 8 bajtów

44‘²!*ḍ@

Wypróbuj online! Pamiętaj, że przypadki testowe 11111 i nowsze są dla TIO trochę za dużo.

Weryfikacja

$ source="34,34,fc,82,21,2a,d5,40"
$ xxd -ps -r > 2017.jelly <<< $source
$ xxd -g 1 2017.jelly
0000000: 34 34 fc 82 21 2a d5 40                          44..!*.@
$ eval printf '"%d "' 0x{$source}; echo # Code points in decimal
52 52 252 130 33 42 213 64
$ test_cases="1 2 80 2017 2019 2027 11111 45183 102349 999999 1234567 4068289"
$ for n in $test_cases; do printf "%11d: %d\n" $n $(jelly f 2017.jelly $n); done
      1: 1
      2: 1
     80: 1
   2017: 1
   2019: 1
   2027: 0
  11111: 1
  45183: 0
 102349: 0

Walizka testowa 999999 działa od 13 godzin. Jestem pesymistą jeśli chodzi o obliczenia 2025! ^4068289 ...

Jak to działa

44‘²!*ḍ@  Main link. Argument: n

44        Yield 44.
  ‘       Increment to yield 45.
   ²      Square to yield 2025.
          Note that no integers in [2018, ..., 2025] are prime numbers.
    !     Take the factorial of 2025.
     *    Raise it to the n-th power.
          This repeats all prime factors in 2025! at least n times, so the result
          will be divisible by n if (and only if) all of its prime factors fall
          in the range [1, ..., 2025].
      ḍ@  Test the result for divisibility by n.

Galaretka , 8 znaków, 14 bajtów UTF-8

Æf½ṀḤ<90

Wypróbuj online!

Jelly zwykle używa własnej strony kodowej dla programów. Jednak większość jego wbudowanych funkcji związanych z liczbami głównymi zaczyna się od Æ, czyli codepoint 13; niezbyt pomocny. Na szczęście interpreter obsługuje również UTF-8, który ma bardziej przyjazne kodowanie.

Weryfikacja

Ten program, w UTF-8, zrzuty heksadecymalne:

00000000: c386 66c2 bde1 b980 e1b8 a43c 3930  ..f........<90

Weryfikacja, czy wszystkie bajty są złożone:

$ for x in c3 86 66 c2 bd e1 b9 80 e1 b8 a4 3c 39 30; do factor $((0x$x)); done
195: 3 5 13
134: 2 67
102: 2 3 17
194: 2 97
189: 3 3 3 7
225: 3 3 5 5
185: 5 37
128: 2 2 2 2 2 2 2
225: 3 3 5 5
184: 2 2 2 23
164: 2 2 41
60: 2 2 3 5
57: 3 19
48: 2 2 2 2 3

Weryfikacja, czy wszystkie punkty kodowe Unicode są złożone:

$ perl -Mutf8 -E '$a = ord, print `factor $a` for split //, "Æf½ṀḤ<90"'
198: 2 3 3 11
102: 2 3 17
189: 3 3 3 7
7744: 2 2 2 2 2 2 11 11
7716: 2 2 3 643
60: 2 2 3 5
57: 3 19
48: 2 2 2 2 3

Jedyny token analizowany jako liczba to 90. Żadne z 9, 0i nie 90są najważniejsze.

Wyjaśnienie

Główny wgląd matematyczny tutaj polega na tym, że 45² to 2025 r., Który zgrabnie przypada między 2017 r. (Bieżącym rokiem) a 2027 r. (Następną liczbą pierwszą). Możemy zatem wziąć pierwiastek kwadratowy z każdego pierwiastka liczbowego liczby i sprawdzić, czy którykolwiek przekroczy 45. Niestety, nie możemy pisać z 45powodu literału 5, więc musimy go podwoić i porównać z 90.

Æf½ṀḤ<90
Æf        In the list of prime factors,
  ½       taking the square root of each element
   Ṁ      then taking the largest element
    Ḥ     and doubling it
     <90  produces a result less than 90.

Mathematica, 62 58 55 bajtów

Ostatnie trzy zapisane bajty pochodzą całkowicie od Martina Endera!

#4<4||#<44*46&&#6[#^-1#4]&[Divisors[#][[6-4]],,,#,,#0]&

Nienazwana funkcja przyjmująca dodatni argument liczby całkowitej i zwracająca Truelub False.

Algorytm rekurencyjny, który #4<4jest prawdziwym przypadkiem podstawowym (potrzebujemy go tylko, aby powrócić Truena imput 1, ale dodatkowe przypadki podstawowe są w porządku). W przeciwnym razie obliczamy drugi najmniejszy dzielnik (który jest koniecznie liczbą pierwszą) wejścia za pomocą Divisors[#][[6-4]]; jeśli jest większa niż 2024 ( 44*46), to wychodzimy z False, w przeciwnym razie wywołujemy funkcję rekurencyjnie (używając #6set to #0) na danych wejściowych podzielonych przez ten mały czynnik pierwszy #(który musimy wyrazić jako #^-1iloczyn wejściowy #4, ponieważ /jest niedozwolony).

Strukturalnie, pierwsza połowa #4<4||#<44*46&&#6[#^-1#4]&jest anonimowa funkcja sześciu argumentów, nazywany z argumentami Divisors[#][[6-4]], Null, Null, #, Null, i #0; jest to, aby ominąć zakaz na znaki 2, 3i 5.

Poprzednia wersja, która oszczędzała cztery bajty, zastępując 8018-6000je 44*46, inspirowana odpowiedzią Jelly ais523 (Martin Ender również wydawał się zainspirowany komentarzem ais523):

#<4||Divisors[#][[6-4]]<44*46&&#0[Divisors[#][[6-4]]^-1#]&

To było dość paskudne: wciąż nie wiem, jak ustawić zmienną w Mathematica pod tymi ograniczeniami! Zarówno =oraz ew Setsą niedozwolone. Unikanie +i )stanowiło również problem, ale nie było zbyt trudne do obejścia kosztem większej liczby bajtów.

Haskell, 48 47 bajtów

\n->[snd$[product[1..44*46]^n]!!0`divMod`n]<[1]

Zasadniczo tłumaczenie odpowiedzi galaretki Dennisa . xnor zapisał bajt.

Zastosowania […]!!0jako nawiasach ponieważ )jest zakazane, a snd+ divMod, ponieważ mw modi remjest zakazane.

Pyke, 10 8 7 9 bajtów

P_Z|hwMX<

Wypróbuj tutaj!

Zaoszczędzono 1 bajt, wykorzystując metodę Dennisa do generowania 2025

P         -     factors(input)
 _        -    reversed(^)
  Z|      -   ^ or 0
    h     -  ^[0] or 1
        < - ^ < V
     wM   -  ⁴45 (ord("M")-32)
       X  -  ^**2

Brachylog , 9 10 bajtów

*$ph$r*<90

Wypróbuj online!

Zasadniczo używając tego samego algorytmu, co moja inna odpowiedź. $phznajduje pierwszy ( h) czynnik pierwszy ( $p); jest to największy czynnik główny, ponieważ listy czynników pierwszych Brachylog zmieniają się z największych na najmniejsze. Następnie biorę pierwiastek kwadratowy ( $r), double ( *) i sprawdzam, czy jest mniejszy niż 90 ( <90).

Najpierw musiałem podwoić dane wejściowe, ponieważ 1 nie ma czynników pierwszych (a zatem nie ma pierwszego czynnika pierwszego). Dodaje to dodatkowy współczynnik liczby podstawowej 2, który nie ma wpływu na to, czy liczba jest krucha w 2017 r., Ale zapobiega awarii podczas obsługi 1.

Właściwie 9 bajtów

τyM:44u²≥

Dzięki Dennis za wiele bajtów!

Wypróbuj online!

Wyjaśnienie:

τyM:44u²≥
τyM        largest prime factor of 2*input (doubled to deal with edge case of n = 1)
   :44u²   2025 (2027 is the next prime after 2017, so any number in [2017, 2026] can be used here - 2025 is very convenient)
        ≥  is 2025 greater than or equal to largest prime factor?

Mathematica, 66 74 bajtów

Dzięki Dennisowi za wskazanie, że U+F4A1jest to zabronione.

Fold[Function[{x,d},And[x,Tr[Divisors@d^0]>6-4||d<44*46]],0<1,Divisors@#]&

Wyjaśnienie:

Divisors@#: Lista dzielników całkowitych pierwszego argumentu #.

0<1: Golf dla True(unika także użycia litery e).

Divisors@d^0: Lista formularza {1, 1, ..., 1}o długości równej liczbie dzielników d.

Tr: W przypadku płaskiej listy Trzwraca sumę tej listy. W ten sposób Tr[Divisors@d^0]zwraca liczbę dzielników d.

Function[{x,d},And[x,Tr[Divisors@d^0]>6-4||d<44*46]]: Funkcja anonimowa z dwoma argumentami xi d. Chodzi o to, że djest dzielnikiem #i testujemy, czy jest on złożony, czy mniejszy, czy równy 2017(włącznie). 2017- kruchość jest równoważna wszystkim dzielnikom spełniającym ten warunek. Jak odkryto ais523 , bycie liczbą pierwszą mniejszą lub równą 2017jest równoważne byciu liczbą pierwszą mniejszą niż 2025. Jak zauważył Greg Martin , wystarczy sprawdzić, czy jest mniejszy niż 2024=44*46. Argument xdziała jak akumulator wskazujący, czy wszystkie dotychczasowe dzielniki spełniają tę właściwość. Następnie opuściliśmy Foldtę funkcję przez wszystkie dzielniki o #wartości początkowejTrue, ponieważ nie mamy dostępu ani do Mapani /@.

05AB1E , 10 bajtów

fθ46n99-›È

Zwraca 1 jeśli prawda, 0 w przeciwnym razie.

Wypróbuj online!

Wyjaśnienie

f          # Push the list of prime factors (ordered)
 θ         # Get the last element
  46n99-   # Push 2017 (46² - 99)
        >  # Push 1 if the last prime factor is greater than 2017, 0 otherwise
         È # Is the resulting number even ? Transforms 1 to 0 and 0 to 1.
           # Implicit display

MATL , 15 bajtów

t:\~ftZp*44QU<A

Dane wyjściowe 0dla produktów sypkich 12017 lub dla produktów sypkich 2017.

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

Ten program sprawdza, czy wszystkie bajty są złożone.

Wyjaśnienie

t       % Implicit input n. Duplicate
:       % Range [1 2 ... n]
\       % Modulo. Gives 0 for divisors of n
~f      % Indices of zero values
t       % Duplicate
Zp      % Is-prime. Gives 1 for primes, 0 for composites
*       % Multiply
44QU    % 44, add 1, square: 2025
<       % Less than, element-wise
A       % True (1) if all entries are nonzero

Bash, 144 bajty

Kodowanie ASCII:

{
printf '[ '
`tr D-Z _-z <<<KFH`tor $1|tr -d :|`tr B-Z _-z <<<JUH`p -o '[0-9]*$'
printf ' -lt $[24*86-46] ]'
}|tr \\n \ |`tr B-Z _-z <<<EDVK`

Jak zwykle w przypadku powłoki, kod wyjścia wskazuje powodzenie (0) lub niepowodzenie (inne niż 0).

Jest to w rzeczywistości inna pisownia

[ factor $1|tr -d :|grep -o '[0-9]*$' -lt 2018 ]

Dostajemy największy czynnik z factor $1|grep -o '[0-9]*$'; tr -d :jest szczególnym przypadku dla-wejściowy 1.

Wyrażenie $[6*6*69-466]przyjmuje wartość do 2018 r.

Używanie trnazw poleceń i używanie ich zastępowania było trudne - nie mogłem użyć formy zagnieżdżenia $( ), więc skończyłem z potokiem do innego Basha, aby ocenić wynik.

Wyniki testów:

$ for i in 1 2 80 2017 2019 2027 11111 45183 102349 999999 1234567 4068289; do printf '%d %s\n' $i `./105241.sh $i  && echo true || echo false`; done
1 true
2 true
80 true
2017 true
2019 true
2027 false
11111 true
45183 false
102349 false
999999 true
1234567 false
4068289 true

Potwierdzenie kodów znaków:

$ grep -v '^#' ./105241.sh | perl -n -Mutf8 -E '$a = ord, print `factor $a` for split //, $_' | grep -v ': .* ' | wc -l
0

Pyth, 11 bajtów

!s>R^h44h1P

Wypróbuj online. Zestaw testowy.

Korzysta ze sztuczki Dennisa, aby uzyskać 2025, a następnie sprawdza, czy nie ma większych czynników wejściowych.

Julia 0,4 , 84 38 37 bajtów

n->1^n:44*46|>prod|>t->t^n-t^n÷n*n<1

Oczekuje argumentu BigInt .

Wypróbuj online! lub sprawdź, czy żaden bajt nie jest liczbą pierwszą .

Japt , 14 bajtów

k æ¨44*46 ?0:1

Zwraca 1 jeśli prawda, 0 jeśli fałsz.

Wypróbuj tutaj .

Braingolf , 11 bajtów [bardzo niekonkurencyjny]

VRp#ߢ-?0:1

Wypróbuj online!

Nieczytelne z powodu tego, ߢktóre śruby z cyframi, jednak nadal działa w tłumaczu.

Nawet nie zauważyłem ograniczeń postaci, kiedy to napisałem, ale wszystko, co musiałem zrobić, to zmienić dziwną postać Unicode z 2017 na 2018.

Biorąc pod uwagę, że 2018 nie jest liczbą pierwszą, każda liczba pierwsza <= 2018jest również<= 2017

Wyjaśnienie

VRp#ߢ-?0:1  Implicit input from command-line args
VR            Create stack2, return to stack1
  p           Split last item into prime factors, push each one to stack in asc order
   #ߢ         Push 2018
     -      Subtract last 2 items (highest prime factor - 2017)
      ?     If last item > 0..
       0    ..push 1
        :   Else..
         1  ..Push 1
            Implicit output of last item on stack