Jedna z moich ulubionych definicji liczb pierwszych jest następująca:

2 jest najmniejszą liczbą pierwszą.
Liczby większe niż 2 są liczbą pierwszą, jeśli nie można ich podzielić przez mniejszą liczbę pierwszą.

Jednak ta definicja wydaje się dowolna, dlaczego 2? Dlaczego nie jakiś inny numer? Cóż, spróbujmy jeszcze kilka liczb, które zdefiniują n-prime, takie jak

n jest najmniejszą n-liczbą pierwszą.
Liczby większe niż n są liczbą n-pierwszą, jeśli nie można ich podzielić przez mniejszą liczbę n-pierwszą.

Zadanie

Zadanie polega na napisaniu programu, który przyjmuje dwa wejścia, dodatnią liczbę całkowitą n i dodatnią liczbę całkowitą a . Następnie zdecyduje, czy a jest n- prime. Twój program powinien wypisać dwie różne wartości: jedną dla „tak, to n-pierwsza”, a drugą dla „nie, to nie n-pierwsza”.

To jest pytanie w golfa kodu, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Testy

Oto listy pierwszych 31 liczb pierwszych dla n = 2 do n = 12 (1 to jedyna liczba pierwsza)

n=2: [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]
n=3: [3,4,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]
n=4: [4,5,6,7,9,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113]
n=5: [5,6,7,8,9,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113]
n=6: [6,7,8,9,10,11,13,15,17,19,23,25,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107]
n=7: [7,8,9,10,11,12,13,15,17,19,23,25,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107]
n=8: [8,9,10,11,12,13,14,15,17,19,21,23,25,29,31,35,37,41,43,47,49,53,59,61,67,71,73,79,83,89,97]
n=9: [9,10,11,12,13,14,15,16,17,19,21,23,25,29,31,35,37,41,43,47,49,53,59,61,67,71,73,79,83,89,97]
n=10: [10,11,12,13,14,15,16,17,18,19,21,23,25,27,29,31,35,37,41,43,47,49,53,59,61,67,71,73,79,83,89]
n=11: [11,12,13,14,15,16,17,18,19,20,21,23,25,27,29,31,35,37,41,43,47,49,53,59,61,67,71,73,79,83,89]
n=12: [12,13,14,15,16,17,18,19,20,21,22,23,25,27,29,31,33,35,37,41,43,47,49,53,55,59,61,67,71,73,77]

— Kreator pszenicy
źródło

4

n=6, a=15to pierwszy interesujący przypadek testowy.

— Neil,

6

Jest to pierwsze miejsce, w którym rozkład non-pattern „a jest n-liczba pierwsza iff n ≤a <2n lub (a≥2n i a jest liczba pierwsza)” ulega rozkładowi.

— Misza Ławrow

2

„Liczby większe niż 2 są liczbą pierwszą, jeśli nie można ich podzielić przez mniejszą liczbę pierwszą”. - Ta definicja pozwala, aby dowolna liczba była liczbą pierwszą. Może chcesz powiedzieć iff zamiast jeśli ?

5

@ThePirateBay Nie mam na myśli dokładnego matematycznego znaczenia tego słowa. Zostawię to.

— Wheat Wizard

1

@JeppeStigNielsen Nie jest to trudne do udowodnienia. Wszystkie liczby zespolone n-pierwsze muszą mieć tylko czynniki pierwsze mniejsze niż n. Wiemy również, że żaden podzbiór ich czynników nie może mieć produktu większego niż n, ponieważ nasza liczba byłaby przez to podzielna. Zatem każda n-pierwsza jest albo 2-pierwsza, albo iloczyn 2 liczb mniejszych niż n. Istnieje tylko skończona liczba par liczb mniejszych niż n, dlatego istnieje tylko skończona liczba złożonych liczb n-pierwszych. Mam nadzieję, że to ma sens, musiałem skrócić, aby dopasować to w komentarzu.

— Wheat Wizard

9

Haskell , 45 bajtów

n!a=not$any(n!)[x|x<-[n..a-1],mod a x<1]||n>a

Wypróbuj online!

Definiuję miłą funkcję rekurencyjną (!):

n!asprawdza, czy którykolwiek z czynników aw zakresie [n,a-1]jest an n-prime. Następnie neguje wynik. Zapewnia to równieżn>a

— H.PWiz
źródło

Oto trochę konkurencji

— Wheat Wizard

@WheatWizard Miałem nadzieję, że ktoś opublikuje krótsze rozwiązanie :)

— H.PWiz

6

Python 2 , 39 37 bajtów

Dzięki Halvard Hummel za -2 bajty.

f=lambda n,i:n==i or i>i%n>0<f(n+1,i)

Wypróbuj online!

— ovs
źródło

4

Python 3 , 45 bajtów

lambda i,k:(i>k)<all(k%r for r in range(i,k))

Wypróbuj online!

Jak to działa

To przyjmuje dwie liczby całkowite jako dane wejściowe, i i k . Najpierw sprawdza, czy k ≥ i . Następnie generuje zakres [i, k) i dla każdej liczby całkowitej N w tym zakresie sprawdza, czy N jest coprime do k . Jeżeli spełnione są oba warunki, to k to ja -prime.

— Pan Xcoder
źródło

Nie możesz używać &zamiast andi >=izamiast >i-1?

— Wheat Wizard

@WheatWizard >=i ma nadal 4 bajty (ze względu na miejsce).

— Neil

@ Nee Jeśli zmienisz się &, nie potrzebujesz miejsca.

— Wheat Wizard

4

Łuska , 6 5 bajtów

εf≥⁰Ḋ

Wypróbuj online! lub zobacz wyniki do 80 .

Dzięki Leo za -1 bajt.

Wyjaśnienie

εf≥⁰Ḋ  Inputs are n and k.
    Ḋ  Divisors of k.
 f     Keep those that are
  ≥⁰   at least n.
ε      Is the result a one-element list?

— Zgarb
źródło

4

R , 44 37 bajtów

function(a,n)a==n|a>n&all(a%%n:(a-1))

Wypróbuj online!

-7 bajtów dzięki Giuseppe

Zwraca TRUEjeśli

ajest równe nlub ( a==n|)
ajest większa niż n i ( a>n&) dla każdej liczby k od ndo a-1, anie jest równomiernie podzielna przez k ( all(a%%n:(a-1)))

Zwraca FALSEinaczej

— duckmayr
źródło

Witamy w PPCG! Świetna pierwsza odpowiedź!

— FantaC,

3

J, 30 bajtów

>:*(-{1=[:+/0=[:|/~]+i.@[)^:>:

Wypróbuj online!

Pobiera wartość początkową jako prawy argument i wartość do sprawdzenia przy lewym argumencie.

Zrozumiałem pierwotnie i nie uwzględniłem mniejszych argumentów niż liczba początkowa. Jestem trochę niezadowolony z długości mojego rozwiązania.

Wyjaśnienie

Niech xbędzie lewym argumentem (wartością do sprawdzenia) i yprawym argumentem (liczba początkowa).

>:*(-{1=[:+/0=[:|/~]+i.@[)^:>:
                          ^:>:  Execute left argument if x >= y
                     i.@[         Create range [0..x]
                   ]+             Add y to it (range now: [y..x+y])
                |/~               Form table of residues
            0=                    Equate each element to 0
          +/                      Sum columns
      1=                          Equate to 1
    -{                            Take the element at position x-y
>:*                             Multiply by result of x >= y

Notatki

Element w pozycji x-yjest wynikiem testu pierwotności dla x(ponieważ dodaliśmy ydo pierwotnego zakresu).

Pomnożenie przez x >: ygwarantuje, że otrzymamy wartość falsey ( 0) za xmniej niż y.

— kapusta
źródło

3

JavaScript (ES6), 33 32 30 bajtów

Pobiera dane wejściowe w składni curry (n)(a). Zwraca wartość logiczną.

n=>p=(a,k=a)=>k%--a?p(a,k):a<n

Próbny

Pokaż fragment kodu

let f =

n=>p=(a,k=a)=>k%--a?p(a,k):a<n

for(n = 2; n <= 12; n++) {
  for(a = n, P = []; P.length < 31; a++) {
    f(n)(a) && P.push(a);
  }
  O.innerText += 'n=' + n + ': ' + P.join(',') + '\n';
}

<pre id=O></pre>

Rozwiń fragment kodu

— Arnauld
źródło

3

Haskell , 30 bajtów

2 bajty zaoszczędzone dzięki pomysłowi H.PWiz, który został zapożyczony z odpowiedzi flawr

n!a=[1]==[1|0<-mod a<$>[n..a]]

Wypróbuj online!

Ok, odkąd minęło trochę czasu, a jedyna jak dotąd odpowiedź Haskell to 45 bajtów, postanowiłem opublikować własną odpowiedź.

Wyjaśnienie

Ta funkcja sprawdza, czy jedyną liczbą między n a a , przez którą można podzielić a, jest sama.

Teraz w definicji wspomniano tylko n- primes mniejsze niż a , więc dlaczego sprawdzamy te wszystkie dodatkowe liczby? Czy nie będziemy mieć problemów, gdy a jest podzielne przez jakiś n- kompozyt większy niż n ?

Nie zrobimy tego, ponieważ jeśli n- kompozyt jest większy niż n, to z definicji musi być podzielny przez mniejszą n- pierwszą. Tak więc, jeśli dzieli tak musi mniejszy n -prime.

Jeśli a jest mniejsze niż n [n..a] , []nie może być równe, [1]co powoduje niepowodzenie sprawdzania.

— Kreator pszenicy
źródło

1

Galaretka , 8 bajtów

rṖ⁴%$Ạ×<

Wypróbuj online!

— Cairney Coheringaahing
źródło

1

Pip , 23 19 14 bajtów

b>=a&$&b%(a,b)

Najkrótszą metodą jest port odpowiedzi Pythona pana Xcodera . Pobiera najmniejszą liczbę pierwszą i liczbę do przetestowania jako argumenty wiersza poleceń. Wypróbuj online!

— DLosc
źródło

1

C, 55 bajtów

f(n,a,i){for(i=a;i-->n;)a%i||f(n,i)&&(i=0);return-1<i;}

Wypróbuj online!

53 bajty, jeśli dozwolonych jest wiele prawdziwych wartości zwracanych:

f(n,a,i){for(i=a;i-->n;)a%i||f(n,i)&&(i=0);return~i;}

Wypróbuj online!

— Steadybox
źródło

1

dc , ₄₀ ₃₄ 37 bajtów

[0p3Q]sf?se[dler%0=f1+dle>u]sudle>u1p

Dołączyłbym link TIO, ale wydaje się, że TIO ma błędną dystrybucję, dcwidząc, jak to działa zgodnie z przeznaczeniem w moim systemie, ale Qpolecenie działa niepoprawnie na TIO. Zamiast tego znajduje się link do bashpoligonu testowego z poprawnie działającą wersją dc:

Demo It!

— R. Kap
źródło

1

APL (Dyalog) , 24 bajty

{⍵∊o/⍨1=+/¨0=o|⍨⊂o←⍺↓⍳⍵}

Wypróbuj online!

W jaki sposób?

⍳⍵- 1doa

o←⍺↓- ndo a, zapisz doo

o|⍨⊂o- modulo każdy element oz każdym elementem wo

0=- sprawdź, gdzie to się równa 0(dzieli)

+/¨ - zsumuj liczbę działów

1= - jeśli mamy tylko jeden, to liczba jest dzielona tylko przez siebie

o/⍨ - więc zachowujemy te zdarzenia

⍵∊- jest aw tej tablicy resztkowej?

— Uriel
źródło

0

JavaScript (Node.js) , 27 bajtów

i=>f=n=>i==n||i>i%n&&f(n+1)

Wypróbuj online!

Port mojej odpowiedzi w Pythonie, pobiera dane wejściowe w składni curry: m(number)(first prime)

— ovs
źródło

0

JavaScript ES5, 34 bajty

for(a=i=(p=prompt)();a%--i;);i<p()

— l4m2
źródło

0

Dodaj ++ , 20 bajtów

L,2Dx@rBcB%B]b*!!A>*

Wypróbuj online!

L,   - Create a lambda function
     - Example arguments:  [5 9]
  2D - Copy below; STACK = [5 9 5]
  x  - Repeat;     STACK = [5 9 [9 9 9 9 9]]
  @  - Reverse;    STACK = [[9 9 9 9 9] 5 19] 
  r  - Range;      STACK = [[9 9 9 9 9] [5 6 7 8 9]]
  Bc - Zip;        STACK = [[9 5] [9 6] [9 7] [9 8] [9 9]]
  B% - Modulo;     STACK = [4 3 2 1]
  B] - Wrap;       STACK = [[4 3 2 1]]
  b* - Product;    STACK = [24]
  !! - Boolean;    STACK = [1]
  A  - Arguments;  STACK = [1 5 9]
  >  - Greater;    STACK = [1 1]
  *  - Product;    STACK = [1]

— Cairney Coheringaahing
źródło

Różne sposoby definiowania liczb pierwszych

Zadanie

Testy

Haskell , 45 bajtów

Python 2 , 39 37 bajtów

Python 3 , 45 bajtów

Jak to działa

Łuska , 6 5 bajtów

Wyjaśnienie

R , 44 37 bajtów

J, 30 bajtów

Wyjaśnienie

Notatki

JavaScript (ES6), 33 32 30 bajtów

Próbny

Haskell , 30 bajtów

Wyjaśnienie

Galaretka , 8 bajtów

Pip , 23 19 14 bajtów

C, 55 bajtów

dc , 40 34 37 bajtów

APL (Dyalog) , 24 bajty

JavaScript (Node.js) , 27 bajtów

JavaScript ES5, 34 bajty

Dodaj ++ , 20 bajtów

dc , ₄₀ ₃₄ 37 bajtów