Znalezienie liczb niecodziennych

17

Twoim wyzwaniem, jeśli zdecydujesz się je zaakceptować, jest kodowanie w golfa funkcji, która zwraca wartość prawda lub fałsz (lub podobną znaczącą reprezentację tak i nie), jeśli liczba spełnia następujące kryteria:

  1. Sama liczba całkowita jest liczbą pierwszą LUB
  2. Każda z liczb całkowitych sąsiada jest liczbą pierwszą

Na przykład:
dane wejściowe 7zwracają wartość True.
Dane wejściowe 8zwracałyby również wartość True.
Dane wejściowe 15zwracają wartość False. (Ani 14, 15, ani 16 nie są liczbami pierwszymi)

Dane wejściowe muszą być w stanie poprawnie zwracać dla liczb od 2 ^ 0 do 2 ^ 20 włącznie, więc nie musisz się martwić o problemy ze znakami lub przepełnienia liczb całkowitych.

Pan Llama
źródło
Przepełnienia liczb 32-bitowych, nie przepełnienia bufora, tak myślę.
użytkownik nieznany
Ups, oznaczało „przepełnienie liczb całkowitych”. Mózg przeszedł na autopilota.
Pan Llama,

Odpowiedzi:

11

J, 17

*/<:$&q:(<:,],>:)

Zwraca wartości logiczne zakodowane jako kody powrotu procesu: zero dla wartości true, zero dla wartości false. Przykładowe użycie:

   */<:$&q:(<:,],>:) 7
0
   */<:$&q:(<:,],>:) 8
0
   */<:$&q:(<:,],>:) 15
3
JB
źródło
*/0 p:<:,],>:jest krótsza, a właściwą funkcją (lambda) jest([:*/0 p:<:,],>:)
randomra
9

Haskell, 47 znaków

f n=any(\k->all((>0).mod k)[2..k-1])[n-1..n+1]
hammar
źródło
6

Python 85 80

def f(n):g=lambda n:all(n%i!=0for i in range(2,n));return g(n)or g(n-1)or g(n+1)

Pierwszy raz na Code Golf, więc pewnie brakuje mi kilku sztuczek.

Kris Harper
źródło
Możesz usunąć []. wszyscy będą bardziej niż zadowoleni z pracy z wyrażeniem generatora. Jeśli nie przeszkadza ci, że Twój kod jest brzydki, możesz również usunąć spacje między 0oraz for, )i or.
stranac
@stranac Awesome. Dziękuję Ci bardzo.
Kris Harper
3
Wprowadziłem kilka prostych zmian, mam nadzieję, że nadal działa:f=lambda n:any(all(m%i for i in range(2,m))for m in[n,n-1,n+1])
Nabb
@Nabb Bardzo miło. Dobra robota.
Kris Harper
5

Nie jest prawdziwym konkurentem pod względem skrótu kodu w jakikolwiek sposób, ale wciąż poddaje się, ponieważ określa prymat za pomocą wyrażenia regularnego jest pokręcone na wiele sposobów!

Python (2.x), 85 znaków

import re
f=lambda n:any(not re.match(r"^1?$|^(11+?)\1+$","1"*x)for x in[n,n-1,n+1])
ChristopheD
źródło
Możesz usunąć pętlę for i wbudować ją w wyrażenie regularne, testując „1” * (n + 1), ale zaczynając od ^ 1? 1? zamiast.
Howard,
4

Rubin (55 lub 50 jako lambda)

def f q;(q-1..q+1).any?{|n|(2..n-1).all?{|d|n%d>0}};end

lub jako lambda (użyj, g[23]aby to nazwać)

g=->q{(q-1..q+1).any?{|n|(2..n-1).all?{|d|n%d>0}}}

Coffeescript (53)

p=(q)->[q-1..q+1].some (n)->[2..n-1].every (d)->n%d>0
jsvnm
źródło
<pedantic> Powinno to być „proc”, a nie „lambda” </pedantic> ;-)
Klamka
3

Nudna Mathematica, 35 rozwiązanie!

PrimeQ[n-1]||PrimeQ[n]||PrimeQ[n+1]
Ry-
źródło
15
Przynajmniej możesz w to zagrać w golfa Or@@PrimeQ/@{n-1,n,n+1}.
Howard
To nie jest funkcja.
Martin Ender,
@ MartinBüttner: Przepraszam, nie znam Mathematiki.
RY-
2
Korzystając z wersji Howarda Or@@PrimeQ@{#-1,#,#+1}&(cięcie w jego kodzie nie jest potrzebne)
Martin Ender
3

C 112 82 72 znaków

Po komentarzu Ilmari Karonena, zapisując 30 znaków, usuwając main, teraz Pzwraca true / false. Zastąpiłem również pętlę rekurencją i trochę więcej poprawek.

p(n,q){return++q==n||n%q&&p(n,q);}P(n){return p(-~n,1)|p(n,1)|p(~-n,1);}

Orginalna wersja:

p(n,q,r){for(r=0,q=2;q<n;)r|=!(n%q++);return!r;}
main(int n,int**m){putchar(48|p(n=atoi(*++m))|p(n-1)|p(n+1));}
ugoren
źródło
Możesz zapisać 2 znaki za pomocą main(n,m)int**m;.
Ilmari Karonen
... a poza tym wyzwanie mówi „kod-golf to funkcja ”.
Ilmari Karonen
3

Mathematica, 24 bajty

Nie wiem, dlaczego ten stary post pojawił się dzisiaj na mojej liście, ale zdałem sobie sprawę, że Mathematica jest tutaj konkurencyjna.

Or@@PrimeQ/@{#-1,#,#+1}&

Nienazwana funkcja przyjmująca argument liczby całkowitej i zwracająca Truelub False. Bezpośrednia realizacja.

Greg Martin
źródło
PrimeQwątki nad listami, więc Or@@PrimeQ@{#-1,#,#+1}&(lub Or@@PrimeQ[#+{-1,0,1}]&) również działa, dla -1 bajtów. (Chociaż wydaje mi się, że nie wiem, czy zostały PrimeQpodzielone na listy w 2012 r.)
Misha Lavrov
3

Stax , 6 bajtów

Ç▀<╝ºΩ

Uruchom i debuguj

Objaśnienie (rozpakowane):

;v:Pv<! Full program, implicit input  Example: 7
;v      Copy input and decrement               7 6
  :P    Next prime                             7 7
    v   Decrement                              7 6
     <! Check if input is >= result            1
pustkowie
źródło
2

JavaScript (71 73 80 )

n=prompt(r=0);for(j=n-2;p=j++<=n;r|=p)for(i=1;++i<j;)p=j%i?p:0;alert(r)

Demo: http://jsfiddle.net/ydsxJ/3/

Edycja 1: Zmień for(i=2;i<j;i++)na for(i=1;++i<j;)(dzięki @minitech). Konwertuj ifinstrukcję na trójskładnikową. Przeniesiono r|=pi p=1na zewnątrz, foraby wyeliminować wewnętrzne szelki. Zapisano 7 znaków.

Edit 2: Kombajny p=1i j++<=ndo p=j++<=n, Zapisz 2 znaków (dzięki @ugoren).

mellamokb
źródło
Możesz użyć for(i=1;++i<j;)zamiast for(i=2;i<j;i++)zapisać 1 dodatkową postać.
Ry-
1
@minitech: !j%inie będzie działać z powodu pierwszeństwa. Działającą alternatywą jest j%i<1.
Nabb
@Nabb: Wow, masz rację. To głupie.
Ry-
Jak o p=j++<=n? Jeśli JavaScript jest tutaj C, powinien działać.
ugoren
@ugoren: Wygląda na to, że zadziałało, dzięki!
mellamokb
2

Regex (ECMAScript), 20 bajtów

^x?x?(?!(x+)(x\1)+$)

Wypróbuj online!

Powyższa wersja nie obsługuje poprawnie zera, ale zajmuje to tylko 1 dodatkowy bajt:

^x?x?(?!(x+)(x\1)+$)x

Jako dodatkowy bonus, oto wersja, która daje dopasowanie zwrotne 1dla jednego mniejszego niż liczba pierwsza, 2dla 3liczby pierwszej i dla jednej więcej niż liczby pierwszej:

^x?x??(?!(x+)(x\1)+$)x

Wypróbuj online!

Deadcode
źródło
Zakres, o którym mówi pytanie, to „między 2 ^ 0 a 2 ^ 20”, więc 1..2 ^ 20, więc 0 nie ma ...
RosLuP
@RosLuP Właśnie dlatego moja podstawowa odpowiedź to 20 bajtów i nie obsługuje poprawnie 0. Uważam, że wartość wykracza poza precyzyjne określenie pytania i daje bardziej solidne odpowiedzi wraz z odpowiedzią, która minimalnie odpowiada specyfikacji pytania.
Deadcode
Czasami robię to samo (piszę „niepotrzebny” test), ale wydaje się to sprzeczne z myśleniem codegolfa, a ludzie, którzy je piszą, nie są uważani za „poważnych” ...
RosLuP
1
@RosLuP Ale jaka szkoda, jeśli podam minimalną odpowiedź jako moją główną odpowiedź? Czy możesz podać przykłady ludzi, którzy tak myślą? Mogłbym to zrozumieć, gdybym udzielił mojej jedynej odpowiedzi jako solidnej, ale nie robię tego.
Deadcode
1

C #, 96

Zwraca -1,0,1 dla prawdy, wszystko inne jest fałszywe.

Wszelkie sugestie dotyczące skrócenia byłyby wspaniałe!

int p(int q){var r=q-1;for(var i=2;i<r&r<q+2;i++){if(i==r-1)break;if(r%i==0)r+=i=1;}return r-q;}

Rozszerzona forma:

int p(int q){
    var r=q-1;
    for(var i=2;i<r&r<q+2;i++){
        if(i==r-1)break;
        if(r%i==0)r+=i=1;
    }
    return r-q;     
}
Płatki śniadaniowe
źródło
Nie jestem do końca pewien, ale myślę, że można usunąć if(i==r-1)break;i zmienić środek forpętli z i<rna i<r-1. Sprowadziłoby cię to do 82.
Ciaran_McCarthy
1

GolfScript: 26

)0\{.:i,{i\%!},,2=@|\(}3*;

Objaśnienie: Najbardziej wewnętrzny blok {.:i,{i\%!},,2=@|\(} określa, czy wierzch stosu jest liczbą pierwszą, sprawdzając, czy są dokładnie 2 czynniki mniejsze niż szczyt stosu. Następnie rozłącza to z drugim przedmiotem na stosie, który utrzymuje stan, czy liczba pierwsza była jeszcze widoczna. Na koniec zmniejsza liczbę na górze stosu.

Rozpocznij od zwiększenia wartości wejściowej, zainicjowania stanu największej widoczności i powtórz blok 3 razy. Od tego będzie zmniejszyć dwukrotnie, ale zaczęliśmy przez zwiększany, to pokrycie n+1i n-1.

Ben Reich
źródło
1

C #, 87 97 znaków

bool p(int q){return new[]{q-1,q,q+1}.Any(x=>Enumerable.Range(2,Math.Abs(x-2)).All(y=>x%y!=0));}
Steve Clanton
źródło
Nie sądzę, że działa to z 1 lub 2 jako wejściem
Ben Reich,
@BenReich Nie. Musiałem dodać dziesięć znaków, aby to naprawić :(
Steve Clanton
1

CJam, 12 bajtów

CJam jest znacznie młodszy od tego wyzwania, więc ta odpowiedź nie kwalifikuje się do zielonego znacznika wyboru (który i tak powinien zostać zaktualizowany do odpowiedzi randomry). Jednak gra w golfa była naprawdę fajna - zacząłem od 17 bajtów, a następnie trzy razy całkowicie zmieniłem swoje podejście, oszczędzając jeden lub dwa bajty za każdym razem.

{(3,f+:mp:|}

Jest to blok, najbliższy odpowiednik funkcji w CJam, która oczekuje danych wejściowych na stosie i pozostawia 1 (prawda) lub 0 (fałsz) na stosie.

Sprawdź to tutaj.

Oto jak to działa:

(3,f+:mp:|
(          "Decrement the input N.";
 3,        "Push an array [0 1 2].";
   f+      "Add each of those to N-1, to get [N-1 N N+1].";
     :mp   "Test each each element for primality, yielding 0 or 1.";
        :| "Fold bitwise OR onto the list, which gives 1 if any of them was 1.";
Martin Ender
źródło
1

F #, 68 bajtów (niekonkurujące)

let p n=Seq.forall(fun x->n%x>0){2..n-1}
let m n=p(n-1)||p n||p(n+1)

Wypróbuj online!

Dlatego uwielbiam golfa kodowego. Nadal jestem bardzo zielony z F #, ale uczę się bardzo dużo o tym, jak działa język i co może zrobić z tego rodzaju wyzwaniami.

Ciaran_McCarthy
źródło
Dlaczego to nie konkuruje?
Nit
1
Ponieważ nie jestem pewien, czy używam dziś w F # czegokolwiek, czego nie było w okolicy, kiedy zadawano to pytanie w 2012 roku. Przyznaję, że to pedantyczne - nawet paranoiczne. Ale zarabiam na życie programami farmaceutycznymi. Paranoja jest zdrowa. ;)
Ciaran_McCarthy
1
Spójrz na tabelę wersji F # w Wikipedii . W zależności od potrzebnej wersji może być starsza niż pytanie.
1

Siatkówka , 22 bajty

$
1
^1?1?(?!(11+)\1+$)

Wypróbuj online!

Staje się jednoargumentowy jako wejście

TwiNight
źródło
Czyste wyrażenie regularne Retina bije to o 2 bajty .
Deadcode
Wygląda na to, że właśnie to miał na myśli Howard .
Neil
1

Java 8, 83 bajty

n->n==1|p(n-1)+p(n)+p(n+1)>0int p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return--n;}

Zwraca true/ falsejako wartości truey / falsey.

Wypróbuj online.

Objaśnienie:

n->                    // Method with integer parameter and boolean return-type
  n==1                 //  Return whether the input is 1 (edge-case)
  |p(n-1)+p(n)+p(n+1)>0//  Or if the sum of `n-1`, `n`, and `n+1` in method `p(n)` is not 0

int p(int n){          // Separated method with integer as both parameter and return-type
  for(int i=2;i<n;     //  Loop `i` in the range [2, `n`)
    n=n%i++<1?         //   If `n` is divisible by `i`
       0               //    Change `n` to 0
      :                //   Else:
       n);             //    Leave `n` as is
                       //  (After the loop `n` is either 0, 1, or unchanged,
                       //   if it's unchanged it's a prime, otherwise not)
  return--n;}          //  Return `n` minus 1

Tak więc int p(int n)spowoduje to -1za n=0i niepodzielne, i spowoduje n-1za n=1lub pierwsze. Ponieważ p(0)+p(1)+p(2)stanie się -1+0+1 = 0i zwróci fałsz (mimo że 2jest liczbą pierwszą), n=1jest to przypadek skrajny wykorzystujący to podejście.


Pojedyncza pętla bez oddzielnej metody miałaby 85 bajtów :

n->{int f=0,j=2,i,t;for(;j-->-1;f=t>1?1:f)for(t=n+j,i=2;i<t;t=t%i++<1?0:t);return f;}

Zwraca 1/ 0jako wartości truey / falsey.

Wypróbuj online.

Wyjaśnienie:

n->{              // Method with integer as both parameter and return-type
  int f=0,        //  Result-integer, starting at 0 (false)
      j=2,i,      //  Index integers
      t;          //  Temp integer
  for(;j-->-1;    //  Loop `j` downwards in range (2, -1]
      f=          //    After every iteration: Change `f` to:
        t>1?      //     If `t` is larger than 1 (`t` is a prime):
         1        //      Change `f` to 1 (true)
        :         //     Else:
         f)       //      Leave `f` the same
    for(t=n+j,    //   Set `t` to `n+j`
        i=2;i<t;  //   Inner loop `i` in the range [2, t)
      t=t%i++<1?  //    If `t` is divisible by `i`:
         0        //     Change `t` to 0
        :         //    Else:
         t);      //     Leave `t` the same
                  //   (If `t` is still the same after this inner loop, it's a prime;
                  //   if it's 0 or 1 instead, it's not a prime)
  return f;}      //  Return the result-integer (either 1/0 for true/false respectively)
Kevin Cruijssen
źródło
1

Japt , 7 bajtów

´Uô2 dj
´Uô2    // Given the range [U-1..U+1],
     dj // sing "Daddy DJ", uh, I mean, check if any are a prime.

Wypróbuj online!

Gnida
źródło
0

R, 68 znaków

f=function(n){library(gmp);i=isprime;ifelse(i(n-1)|i(n)|i(n+1),1,0)}

Użycie (1 dla PRAWDA, 0 dla FAŁSZ):

f(7)
[1] 1
f(8)
[1] 1
f(15)
[1] 0
Paolo
źródło
1
Naprawdę nie wiem, jak działa R, ale czy mógłbyś to zrobić i(n-1)|i(n)|i(n+1)zamiast ifelse(i(n-1)|i(n)|i(n+1),1,0)?
Ry-
Masz rację: g = funkcja (n) {biblioteka (gmp); i = isprime; i (n-1) | i (n) | i (n + 1)} - do 56 znaków! ;-)
Paolo,
0

C ++

k=3;cin>>i;i--;
while(k)
{l[k]=0;
  for(j=2;j<i;j++)
   if(!(i%j))
     l[k]++;
  k--;
  i++;
}
if(!l[1]|!l[2]|!l[3])
     cout<<"1";
else cout<<"0";
ajobdesh
źródło
Witamy w CodeGold.SE. Jeśli spojrzysz na inne odpowiedzi, zauważysz wspólny format odpowiedzi na pytania [code-golf]. Możesz także zastosować go do swoich odpowiedzi.
dmckee,
0

P, 43 znaki 36

{any min each a mod 2_'til each a:x+-1 0 1}
{any(min')a mod 2_'(til')a:x+-1 0 1}
tartin
źródło
0

J, 16 znaków

   (_2&<@-4 p:]-2:)

   (_2&<@-4 p:]-2:) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1
randomra
źródło
0

Python, 69 67 znaków

any(all(i%j for j in range(2,i))for i in range(input()-1,8**7)[:3])

8**7 > 2**20 będąc nieco krótszym do napisania

Valentin CLEMENT
źródło
0

Rubinowy, 47 znaków, ale bardzo czytelny

require'Prime'
f=->x{[x-1,x,x+1].any? &:prime?}
Klamka
źródło
0

C ++ 97

ugoren zdaje się pobić mnie do sprytnego rozwiązania. Jest trzykrotnie krótką wersją w pętli:

P(int k){int j=1;for(int i=2;i<k;){j=k%i++&&j;}return j;}
a(int b){return P(b)|P(b+1)|P(b-1);}
Nathan Cooper
źródło
0

Dalej (gforth) , 104 bajty

: p dup 1 > if 1 over 2 ?do over i mod 0> * loop else 0 then nip ;
: f dup 1- p over 1+ p rot p + + 0< ;

Wypróbuj online!

Wyjaśnienie

Kontrola wstępna (p)

dup 1 > if          \ if number to check if greater than 1
   1 over 2 ?do     \ place a 1 on the stack to act as a boolean and loop from 2 to n
      over i  mod   \ take the modulo of n and i
      0> *          \ check if greater than 0 (not a divisor) and multiply result by boolean
   loop             \ end the loop, result will be -1 if no divisor was found (prime)
else                \ if n is less than 2
   0                \ put 0 on the stack (not prime)
then                \ end the loop
nip                 \ drop n from the stack

Główna funkcja (f)

dup 1- p             \ get n-1 and check if prime
over 1+ p            \ get n+1 and check if prime
rot p                \ rotate stack to put n on top and check if prime
+ + 0<               \ add the three results and check if less than 0 (at least 1 was prime)
reffu
źródło
0

Galaretka , 5 bajtów

‘r’ẒẸ

Wypróbuj online!

Jak to działa

‘r’ẒẸ    Monadic main link. Input: integer n
‘r’      Generate range n-1..n+1
   ẒẸ    Is any of them a prime?
Bubbler
źródło