Zadanie

Napisz funkcję, która akceptuje dwie liczby całkowite a,breprezentujące liczbę całkowitą Gaussa z = a+ib(liczba zespolona). Program musi zwrócić wartość true lub false, w zależności od tego, czy a+ibjest liczbą pierwszą Gaussa, czy nie .

Definicja:

a + bi jest liczbą pierwszą Gaussa wtedy i tylko wtedy, gdy spełnia jeden z następujących warunków:

• ai boba są niezerowe i a^2 + b^2są liczbą pierwszą
• awynosi zero, |b|jest liczbą pierwszą i|b| = 3 (mod 4)
• bwynosi zero, |a|jest liczbą pierwszą i|a| = 3 (mod 4)

Detale

Powinieneś napisać tylko funkcję. Jeśli twój język nie ma funkcji, możesz założyć, że liczby całkowite są przechowywane w dwóch zmiennych i wydrukować wynik lub zapisać go w pliku.

Nie możesz korzystać z wbudowanych funkcji swojego języka, takich jak isprimelub prime_listlub nthprimelub factor. Najmniejsza liczba bajtów wygrywa. Praca programu musi na a,bktórym a^2+b^2jest 32-bitowy (podpisany) całkowitą i powinna zakończyć się w nie znacznie więcej niż 30 sekund.

Pierwsza lista

Kropki oznaczają liczby pierwsze na płaszczyźnie Gaussa ( x= rzeczywista, y= urojona oś):

Niektóre większe liczby pierwsze:

(9940, 43833)
(4190, 42741)
(9557, 41412)
(1437, 44090)

Haskell - 77/ 108 107 Znaki

użycie: w obu rozwiązaniach wpisanie% b zwróci, czy a + bi jest liczbą pierwszą gaussowską.

najniższy udało mi się, ale brak kreatywności i wydajności (77 znaków)

p n=all(\x->rem n x>0)[2..n-1]
a%0=rem a 4==3&&p(abs a)
0%a=a%0
a%b=p$a^2+b^2

to rozwiązanie obsługuje wszystkie liczby poniżej n, aby sprawdzić, czy jest liczbą pierwszą.

wersja bez golfa:

isprime = all (\x -> rem n x != 0) [2..n-1] -- none of the numbers between 2 and n-1 divide n.
isGaussianPrime a 0 = rem a 4==3 && isprime (abs a)
isGaussianPrime 0 a = isGaussianPrime a 0   -- the definition is symmetric
isGaussianPrime a b = isprime (a^2 + b^2)

następne rozwiązanie ma dodatkową funkcję - zapamiętywanie. po sprawdzeniu, czy liczba całkowita n jest liczbą pierwszą, nie trzeba ponownie obliczać „pierwotności” wszystkich liczb mniejszych lub równych n, ponieważ zostaną one zapisane na komputerze.

(107 znaków. Komentarze są dla jasności)

s(p:x)=p:s[n|n<-x,rem n p>0] --the sieve function
l=s[2..]                     --infinite list of primes
p n=n==filter(>=n)l!!0       --check whether n is in the list of primes
a%0=rem a 4==3&&p(abs a)
0%a=a%0
a%b=p$a*a+b*b

wersja bez golfa:

primes = sieve [2..] where
    sieve (p:xs) = p:filter (\n -> rem n p /= 0) xs
isprime n = n == head (filter (>=n) primes) -- checks if the first prime >= n is equal to n. if it is, n is prime.
isGaussianPrime a 0 = rem a 4==3 && isprime (abs a)
isGaussianPrime 0 a = isGaussianPrime a 0   -- the definition is symmetric
isGaussianPrime a b = isprime (a^2 + b^2)

wykorzystuje to sito Eratostenesa do obliczenia nieskończonej listy wszystkich liczb pierwszych (zwanej l dla listy w kodzie). (nieskończone listy są dobrze znaną sztuczką haskell).

jak można mieć nieskończoną listę? na początku programu lista nie jest oceniana, a zamiast przechowywać elementy list, komputer zapisuje sposób ich obliczenia. ale gdy program uzyskuje dostęp do listy, częściowo ocenia się do żądania. więc jeśli program zażąda czwartego elementu na liście, komputer obliczy wszystkie liczby pierwsze aż do czwartej, które nie zostały jeszcze ocenione, zapisze je, a reszta pozostanie nieoceniona, zapisana jako sposób ich jednokrotnego obliczenia potrzebne.

zwróć uwagę, że wszystko to jest wyrażane swobodnie przez leniwą naturę języka Haskell, czego nie wynika z samego kodu.

obie wersje programu są przeciążone, więc mogą obsługiwać dane o dowolnej wielkości.

C, 149 118 znaków

Wersja edytowana (118 znaków):

int G(int a,int b){a=abs(a);b=abs(b);int n=a*b?a*a+b*b:a+b,
d=2;for(;n/d/d&&n%d;d++);return n/d/d|n<2?0:(a+b&3)>2|a*b;}

To jest jedna funkcja:

• G ( a , b ) zwraca wartość niezerową (prawda), jeśli a + bi jest liczbą pierwszą Gaussa, lub zero (fałsz) w przeciwnym razie.

Składa test pierwszeństwa liczb całkowitych na wyrażenie n/d/d|n<2ukryte w obliczeniu wartości zwracanej. Ten kod do gry w golfa służy również a*bjako zamiennik a&&b(innymi słowy a!=0 && b!=0) i innych sztuczek obejmujących pierwszeństwo operatora i dzielenie liczb całkowitych. Na przykład n/d/djest krótszy sposób mówienia n/d/d>=1, który jest bezpieczny sposób przelewowy powiedzieć n>=d*dlub d*d<=nczy w istocie d<=sqrt(n).

Wersja oryginalna (149 znaków):

int Q(int n){int d=2;for(;n/d/d&&n%d;d++);return n/d/d||n<2;}
int G(int a,int b){a=abs(a);b=abs(b);return!((a|b%4<3|Q(b))*(b|a%4<3|Q(a))*Q(a*a+b*b));}

Funkcje:

• Q ( n ) zwraca 0 (fałsz), jeśli n jest liczbą pierwszą, lub 1 (prawda), jeśli n jest liczbą pierwszą. Jest to funkcja pomocnicza dla G ( a , b ).

• G ( a , b ) zwraca 1 (prawda), jeśli a + bi jest liczbą pierwszą Gaussa, lub 0 (fałsz) w przeciwnym razie.

Wyjściowa próbka (skalowana w górę o 200%) dla | a |, | b | ≤ 128:

APL (Dyalog Unicode) , 36 47 48 49 47 43 28 bajtów

Pobiera tablicę dwóch liczb całkowitych a bi zwraca wartość logiczną instrukcji a+bi is a Gaussian integer.

Edycja: +11 bajtów, ponieważ źle zrozumiałem definicję liczby Gaussa. +1 bajt od ponownego poprawienia odpowiedzi. +1 bajt z trzeciej poprawki błędu. -2 bajty z powodu użycia pociągu zamiast dfn. -4 bajty dzięki ngn dzięki użyciu osłony condition: if_true ⋄ if_falsezamiast if_true⊣⍣condition⊢if_false. -15 bajtów dzięki ngn ze względu na znalezienie zupełnie innego sposobu na napisanie warunku-jeśli-inaczej jako pełnego zestawu.

{2=≢∪⍵∨⍳⍵}|+.×0∘∊⊃|{⍺⍵}3=4||

Wypróbuj online!

Wyjaśnienie

{2=≢∪⍵∨⍳⍵}|+.×0∘∊⊃|{⍺⍵}3=4||

                           |  ⍝ abs(a), abs(b) or abs(list)
                       3=4|   ⍝ Check if a and b are congruent to 3 (mod 4)
                  |{⍺⍵}       ⍝ Combine with (abs(a), abs(b))
              0∘∊⊃            ⍝ Pick out the original abs(list) if both are non-zero
                              ⍝ Else pick out (if 3 mod 4)
          |+.×                ⍝ Dot product with abs(list) returns any of
                              ⍝ - All zeroes if neither check passed
                              ⍝ - The zero and the number that IS 3 mod 4
                              ⍝ - a^2 + b^2
{2=≢∪⍵∨⍳⍵}                    ⍝ Check if any of the above are prime, and return

Haskell - 121 znaków (w tym nowe znaki)

Oto stosunkowo proste rozwiązanie Haskell, które nie korzysta z żadnych zewnętrznych modułów i jest zmarnowane tak daleko, jak tylko mogłem je zdobyć.

a%1=[]
a%n|n`mod`a<1=a:2%(n`div`a)|1>0=(a+1)%n
0#b=2%d==[d]&&d`mod`4==3where d=abs(b)
a#0=0#a
a#b=2%c==[c]where c=a^2+b^2

Wywołaj jako ghci ./gprimes.hsi wtedy możesz użyć go w interaktywnej powłoce. Uwaga: liczby ujemne są wybredne i muszą być umieszczone w nawiasach. To znaczy

*Main>1#1
True
*Main>(-3)#0
True
*Main>2#2
False

Python - 121 120 znaków

def p(x,s=2):
 while s*s<=abs(x):yield x%s;s+=1
f=lambda a,b:(all(p(a*a+b*b))if b else f(b,a))if a else(b%4>2)&all(p(b))

psprawdza, czy abs(x)jest liczbą pierwszą, iterując wszystkie liczby od 2 do abs(x)**.5(co jest sqrt(abs(x))). Robi to, poddając się x % skażdemu s. allnastępnie sprawdza, czy wszystkie uzyskane wartości są niezerowe, i przestaje generować wartości, gdy napotka dzielnik x. W f, f(b,a)zastępuje sprawę do b==0inspirowany @killmous 'Haskell odpowiedź.

-1 znak i poprawka błędu z @PeterTaylor

Python 2.7 , 341 301 253 bajtów, zoptymalizowany pod kątem szybkości

lambda x,y:(x==0and g(y))or(y==0and g(x))or(x*y and p(x*x+y*y))
def p(n,r=[2]):a=lambda n:r+range(r[-1],int(n**.5)+1);r+=[i for i in a(n)if all(i%j for j in a(i))]if n>r[-1]**2else[];return all(n%i for i in r if i*i<n)
g=lambda x:abs(x)%4>2and p(abs(x))

Wypróbuj online!

#pRimes. need at least one for r[-1]
r=[2]
#list of primes and other to-check-for-primarity numbers 
#(between max(r) and sqrt(n))
a=lambda n:r+list(range(r[-1],int(n**.5)+1))
#is_prime, using a(n)
f=lambda n:all(n%i for i in a(n))
#is_prime, using r
def p(n):
    global r
    #if r is not enough, update r
    if n>r[-1]**2:
        r+=[i for i in a(n) if f(i)]
    return all(n%i for i in r if i*i<n)
#sub-function for testing (0,y) and (x,0)
g=lambda x:abs(x)%4==3 and p(abs(x))
#the testing function
h=lambda x,y:(x==0 and g(y)) or (y==0 and g(x)) or (x and y and p(x*x+y*y))

Dzięki: 40 +48 - cała gra w golfa dla Jo Kinga

Perl - 110 107 105 znaków

Mam nadzieję, że poprawnie zastosowałem połączoną definicję ...

sub f{($a,$b)=map abs,@_;$n=$a**(1+!!$b)+$b**(1+!!$a);(grep{$n%$_<1}2..$n)<2&&($a||$b%4>2)&&($b||$a%4>2)}

Nie golfowany:

sub f {
  ($a,$b) = map abs, @_;
  $n = $a**(1+!!$b) + $b**(1+!!$a);
  (grep {$n%$_<1} 2..$n)<2 && ($a || $b%4==3) && ($b || $a%4==3)
}

Wyjaśnienie, że ktoś pyta: czytam argumenty ( @_) i umieścić ich wartości bezwzględne w $a, $bnie dlatego, że funkcja nie trzeba ich znak. Każde z kryteriów wymaga przetestowania pierwotności liczby, ale liczba ta zależy od tego, $aczy$b jest zero, co starałem się wyrazić w najkrótszy sposób i wstawić $n. Na koniec sprawdzam, czy liczba $npierwsza jest liczona, licząc, ile liczb między 2 i sam dzielę ją bez reszty (to jest grep...<2część), a następnie sprawdzam dodatkowo, że jeśli jedna z liczb jest zerowa, to druga równa się 3 modulo 4. Funkcja wartość zwracana jest domyślnie wartością ostatniego wiersza, a te warunki zwracają pewną prawdziwą wartość, jeśli wszystkie warunki zostaną spełnione.

golflua 147 141

Powyższa liczba pomija nowe wiersze, które dodałem, aby zobaczyć różne funkcje. Pomimo nalegań, aby tego nie robić, brutalnie rozwiązuję liczby pierwsze w tych przypadkach.

\p(x)s=2@s*s<=M.a(x)?(x%s==0)~0$s=s+1$~1$
\g(a,b)?a*b!=0~p(a^2+b^2)??a==0~p(b)+M.a(b)%4>2??b==0~p(a)+M.a(a)%4>2!?~0$$
w(g(tn(I.r()),tn(I.r())))

Zwraca 1, jeśli prawda, i 0, jeśli nie.

Nie golfowa wersja Lua,

-- prime number checker
function p(x)
   s=2
   while s*s<=math.abs(x) do
      if(x%s==0) then return 0 end
      s=s+1
   end
   return 1
end

-- check gaussian primes
function g(a,b)
   if a*b~=0 then
      return p(a^2+b^2)
   elseif a==0 then
      return p(b) + math.abs(b)%4>2
   elseif b==0 then
      return p(a) + math.abs(a)%4>2
   else
      return 0
   end
end


a=tonumber(io.read())
b=tonumber(io.read())
print(g(a,b))

APL (NARS), 99 znaków, 198 bajtów

r←p w;i;k
r←0⋄→0×⍳w<2⋄i←2⋄k←√w⋄→3
→0×⍳0=i∣w⋄i+←1
→2×⍳i≤k
r←1

f←{v←√k←+/2*⍨⍺⍵⋄0=⍺×⍵:(p v)∧3=4∣v⋄p k}

test:

  0 f 13
0
  0 f 9
0
  2 f 3
1
  3 f 4
0
  0 f 7
1
  0 f 9
0
  4600 f 5603
1  

Runiczne Zaklęcia , 41 bajtów

>ii:0)?\S:0)?\:*S:*+'PA@
3%4A|'S/;$=?4/?3

Wypróbuj online!

Skończyło się to o wiele łatwiejszym niż myślałem i nie miałem wiele miejsca na golfiację. Oryginalny program, który zablokowałem, to:

>ii:0)?\S:0)?\:*S:*+'PA@
3%4A|'S/!   S/;$=

Bawiłem się, próbując porównać oba wejścia jednocześnie (co pozwoliło zaoszczędzić cały jeden 1 bajt), ale kiedy to wpadnie do sekcji „jeden z nich ma zero”, nie było dobrego sposobu, aby dowiedzieć się, który element było niezerowe w celu wykonania ostatniej kontroli, a tym bardziej sposób na zrobienie tego bez wydawania co najmniej 1 bajtu (bez ogólnych oszczędności).

Mathematica, 149 znaków

If[a==0,#[[3]]&&Mod[Abs@b,4]==3,If[b==0,#[[2]]&&Mod[Abs@a,4]==3,#[[1]]]]&[(q=#;Total[Boole@IntegerQ[q/#]&/@Range@q]<3&&q!=0)&/@{a^2+b^2,Abs@a,Abs@b}]

Kod nie używa żadnych standardowych funkcji liczb pierwszych w matematyce, zamiast tego zlicza liczby całkowite na liście {n / 1, n / 2, ..., n / n}; jeśli liczba wynosi 1 lub 2, n jest liczbą pierwszą. Opracowana forma funkcji:

MyIsPrime[p_] := (q = Abs@p; 
  Total[Boole@IntegerQ[q/#] & /@ Range@q] < 3 && q != 0)

Dodatkowy wykres wszystkich liczb pierwszych Gaussa od -20 do 20:

Rubinowy -rprime , 65 60 80 bajtów

Nie zauważyłem zasady „nie można używać isPrime” ...

->a,b{r=->n{(2...n).all?{|i|n%i>0}};c=(a+b).abs;r[a*a+b*b]||a*b==0&&r[c]&&c%4>2}

Wypróbuj online!

Python - 117 122 121

def f(a,b):
 v=(a**2+b**2,a+b)[a*b==0]
 for i in range(2,abs(v)):
  if v%i<1:a=b=0
 return abs((a,b)[a==0])%4==3or a*b!=0