is_gaussian_prime (z)?

23

Tugas

Tulis fungsi yang menerima dua bilangan bulat a,byang mewakili bilangan bulat Gaussian z = a+ib( bilangan kompleks). Program ini harus kembali benar atau salah tergantung pada apakah a+ibmerupakan perdana Gaussian atau tidak .

Definisi:

a + bi adalah Gaussian prime jika dan hanya jika memenuhi salah satu dari kondisi berikut:

  • adan bkeduanya bukan nol dan a^2 + b^2prima
  • aadalah nol, |b|prima dan|b| = 3 (mod 4)
  • badalah nol, |a|prima dan|a| = 3 (mod 4)

Detail

Anda hanya harus menulis fungsi. Jika bahasa Anda tidak memiliki fungsi, Anda dapat mengasumsikan bahwa bilangan bulat disimpan dalam dua variabel dan mencetak hasilnya atau menulisnya ke file.

Anda tidak dapat menggunakan built-in fungsi bahasa Anda seperti isprimeatau prime_listatau nthprimeatau factor. Jumlah byte terendah menang. Program harus bekerja di a,bmana a^2+b^2bilangan bulat 32 ditandatangani (ditandatangani) dan harus selesai dalam waktu tidak lebih dari 30 detik.

Daftar utama

Titik-titik mewakili bilangan prima pada bidang Gaussian ( x= nyata, y= sumbu imajiner):

masukkan deskripsi gambar di sini

Beberapa bilangan prima yang lebih besar:

(9940, 43833)
(4190, 42741)
(9557, 41412)
(1437, 44090)
cacat
sumber
2
Apakah kami diizinkan menggunakan fungsi factorisation ( factordi Bash, mfdan mFdi CJam, ...)
Oh tidak, saya lupa metode faktorisasi itu ada, tidak tolong tidak =) Dan batas 32bit berlaku untuk ^ 2 + b ^ 2, tidak akan masuk akal sebaliknya. Terima kasih atas masukan Anda! Saya memperbarui pertanyaan.
flawr
2
Saya menambahkan definisi bilangan prima Gaussian ke posting. Jika Anda tidak menyukai cara saya melakukannya, jangan ragu untuk mengembalikannya, tetapi saya pasti akan merekomendasikan untuk memasukkan definisi tersebut di suatu tempat.
undergroundmonorail
Itu bagus, saya awalnya tidak ingin langsung menunjukkan bagaimana menentukan primality agar orang menjadi kreatif =)
flawr
1 1073741857 bagi saya sepertinya bukan perdana Gaussian karena 1 ^ 2 + 1073741857 ^ 2 adalah satu nomor genap ...
RosLuP

Jawaban:

4

Haskell - 77/ 108 107 Karakter

penggunaan: di kedua solusi, mengetikkan% b akan mengembalikan apakah + bi adalah prime gaussian.

terendah yang saya kelola, tetapi tidak ada kreativitas atau kinerja (77 karakter)

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

solusi ini hanya menjalankan semua angka di bawah n untuk memeriksa apakah itu prima.

versi tanpa ungolfed:

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)

solusi berikutnya memiliki fitur tambahan - memoisasi. setelah Anda memeriksa apakah bilangan bulat n adalah bilangan prima, Anda tidak perlu menghitung ulang "nilai" semua angka yang lebih kecil dari atau sama dengan n, karena bilangan itu akan disimpan di komputer.

(107 karakter. Komentar untuk kejelasan)

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

versi tanpa ungolfed:

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)

ini menggunakan saringan Eratosthenes untuk menghitung daftar tak terbatas dari semua bilangan prima (disebut l untuk daftar dalam kode). (Daftar infinite adalah trik haskell yang terkenal).

bagaimana mungkin memiliki daftar yang tidak terbatas? pada awal program, daftar tidak dievaluasi, dan alih-alih menyimpan elemen daftar, komputer menyimpan cara untuk menghitungnya. tetapi ketika program mengakses daftar itu sebagian mengevaluasi sendiri hingga permintaan. jadi, jika program meminta item keempat dalam daftar, komputer akan menghitung semua bilangan prima hingga sebagainya yang belum dievaluasi, menyimpannya, dan sisanya akan tetap tidak dievaluasi, disimpan sebagai cara untuk menghitungnya sekali dibutuhkan.

perhatikan bahwa semua ini diberikan secara bebas oleh sifat malas bahasa Haskell, tidak ada yang terlihat dari kode itu sendiri.

kedua versi program kelebihan beban, sehingga mereka dapat menangani data berukuran sewenang-wenang.

haskeller bangga
sumber
Menurut hitungan saya, solusi pertama Anda sebenarnya 77 karakter: D
killmous
saya menghitung baris baru, bukan?
haskeller bangga
Saya menghitung 74 karakter reguler dan 3 baris baru
killmous
Anda benar, tampaknya karena alasan tertentu notepad ++ menambahkan karakter sebelum baris baru. Terima kasih!
haskeller bangga
itu sebabnya saya menggunakan luhur;) senang membantu!
Killmous
9

C, 149 118 karakter

Versi yang diedit (118 karakter):

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;}

Ini adalah fungsi tunggal:

  • G ( a , b ) mengembalikan bukan nol (benar) jika a + bi adalah prime Gaussian, atau nol (false) sebaliknya.

Ini melipat uji bilangan bulat integer menjadi ekspresi n/d/d|n<2tersembunyi dalam perhitungan nilai kembali. Kode golf ini juga digunakan a*bsebagai pengganti a&&b(dengan kata lain a!=0 && b!=0) dan trik lain yang melibatkan operator diutamakan dan pembagian bilangan bulat. Sebagai contoh n/d/dadalah cara yang lebih singkat untuk mengatakan n/d/d>=1, yang merupakan cara yang aman untuk mengatakan n>=d*datau d*d<=natau pada dasarnya d<=sqrt(n).


Versi asli (149 karakter):

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));}

Fungsi:

  • Q ( n ) mengembalikan 0 (salah) jika n adalah prima, atau 1 (benar) jika n adalah nonprima. Ini adalah fungsi pembantu untuk G ( a , b ).

  • G ( a , b ) mengembalikan 1 (benar) jika a + bi adalah prime Gaussian, atau 0 (false) sebaliknya.

Output sampel (ditingkatkan 200%) untuk | a |, | b | ≤ 128:

Sampel128

Todd Lehman
sumber
2
+1 untuk gambar! Bisakah Anda juga melakukan satu tentang ukuran yang sama hanya di kuadran pertama (karena simetri), itu benar-benar tampak hebat di sini =)
flawr
Anda dapat menyimpan beberapa karakter dengan mengganti d = 2; untuk (; n / d / d && n% d; d ++); dengan untuk (d = 2; n / d / d && n% d ++;);
Alchymist
@Alymymist - Itu memang menyimpan karakter, tetapi menghasilkan hasil yang salah. Sangat penting bahwa d++tidak terjadi sebagai bagian dari kondisi, selain itu mengacaukan logika berikut. Juga, menggerakkan bagian d=2dalam forloop sebenarnya meningkatkan jumlah karakter daripada menguranginya, karena dmasih perlu dinyatakan sebagai intsebelum forloop. Apakah saya melewatkan sesuatu?
Todd Lehman
Terlalu benar Bahaya melihat ini jauh dari lingkungan pengkodean dan tidak cukup dekat. Penambahan harus tetap di tempatnya dan inisialisasi hanya membantu solusi awal Anda. Ada penghematan yang jelas jika Anda mendeklarasikan n & d di luar fungsi, tanpa menentukan int, dan menginisialisasinya dalam for for loop, tetapi saya berasumsi Anda membuat fungsi mandiri yang merupakan interpretasi ketat dari persyaratan.
Alchymist
1
Putaran pengujian utama di sini adalah golf spektakuler! Namun dimungkinkan untuk mencapai lebih banyak penghematan dengan menjatuhkan penspesifikasi tipe int untuk tipe pengembalian dan argumen, menggunakan variabel untuk | a | + | b | dan mengoptimalkan pernyataan kembali: G(a,b){int s=abs(a)+abs(b),n=a*b?a*a+b*b:s,d=2;for(;n/d/d&&n%d;d++);return n>1>n/d/d&&s%4/3|a*b;}keluar hanya 97 karakter.
feersum
4

APL (Dyalog Unicode) , 36 47 48 49 47 43 28 byte

Mengambil array dua bilangan bulat a bdan mengembalikan nilai Boolean pernyataan a+bi is a Gaussian integer.

Sunting: +11 byte karena saya salah memahami definisi perdana Gaussian. +1 byte dari mengoreksi jawaban lagi. +1 byte dari perbaikan bug ketiga. -2 byte karena menggunakan kereta bukan dfn. -4 byte terima kasih kepada ngn karena menggunakan pelindung condition: if_true ⋄ if_falsealih-alih if_true⊣⍣condition⊢if_false. -15 byte berkat ngn karena menemukan cara yang sama sekali berbeda untuk menulis kondisi-jika-selain sebagai kereta penuh.

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

Cobalah online!

Penjelasan

{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
Sherlock9
sumber
3

Haskell - 121 karakter (termasuk baris baru)

Berikut ini adalah solusi Haskell yang relatif sederhana yang tidak menggunakan modul eksternal apa pun dan diturunkan sebanyak yang saya bisa.

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

Aktifkan sebagai ghci ./gprimes.hsdan kemudian Anda dapat menggunakannya di shell interaktif. Catatan: angka negatif rewel dan harus ditempatkan dalam tanda kurung. Yaitu

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

Python - 121 120 karakter

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))

pmemeriksa apakah abs(x)prime dengan mengulangi semua angka dari 2 hingga abs(x)**.5(yang sqrt(abs(x))). Ia melakukannya dengan menghasilkan x % suntuk masing-masing s. allkemudian memeriksa apakah semua nilai yang dihasilkan adalah nol dan berhenti menghasilkan nilai setelah bertemu dengan pembagi x. Dalam f, f(b,a)menggantikan kasing untuk b==0, terinspirasi oleh @killmous 'jawaban Haskell.


-1 char dan perbaikan bug dari @PeterTaylor

hlt
sumber
Senang saya bisa membantu :)
killmous
Anda bisa mengganti s<abs(x)**.5dengan s*s<abs(x)untuk menghemat 2. Meskipun Anda benar-benar harus memeriksa <=, jadi mungkin bermasalah saat ini.
Peter Taylor
@PeterTaylor Terima kasih telah menunjukkan bug ...
hlt
Memanggil f(0,15)hasil TypeError: unsupported operand type(s) for &: 'bool' and 'generator'dengan juru bahasa saya. :(
Falko
f(0,15)memberi Falseuntuk saya, baik pada 2.7.6 dan 3.4.1 (pada OS X). Anda versi apa?
hlt
3

Python 2.7 , 341 301 253 byte, dioptimalkan untuk kecepatan

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))

Cobalah 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))

Terima kasih: 40 +48 - seluruh bermain golf untuk Jo King

Alexey Burdin
sumber
The flambda juga uneccesary, bersama dengan listpanggilan. 257 byte tanpa itu, ditambah beberapa penghapusan spasi putih. Ini mungkin tidak seefisien lagi
Jo King
(15,0) sekarang benar dalam versi 257 byte dan waktu tayang juga meningkat 5,5, maaf
Alexey Burdin
2

Perl - 110 107 105 karakter

Saya harap saya mengikuti definisi yang ditautkan dengan benar ...

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)}

Tidak Disatukan:

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)
}

Penjelasan, karena seseorang bertanya: Saya membaca argumen ( @_) dan memasukkan nilai absolutnya ke dalam $a,$b karena fungsi tidak perlu tanda mereka. Masing-masing kriteria memerlukan pengujian keutamaan angka, tetapi angka ini tergantung pada apakah$a$b nol atau tidak, yang saya coba ekspresikan dengan cara terpendek dan dimasukkan $n. Akhirnya saya memeriksa apakah $nbilangan prima dengan menghitung berapa angka antara 2 dan itu sendiri membaginya tanpa sisa (itu grep...<2bagiannya), dan kemudian memeriksa di samping bahwa jika salah satu bilangan adalah nol maka yang lain sama dengan 3 modulo 4. Fungsinya nilai pengembalian secara default adalah nilai dari baris terakhirnya, dan kondisi ini mengembalikan beberapa nilai kebenaran jika semua kondisi terpenuhi.

Tal
sumber
Saya tidak bisa menjalankannya untuk parameter negatif.
Killmous
1
@ Killmous Anda benar, baru saja memperbaikinya
Tal
dapatkah Anda menjelaskan algoritmenya?
haskeller bangga
1
Bagus! Ngomong-ngomong, saya pikir Anda bisa mencukur beberapa karakter dengan menulis $a%4>2alih-alih $a%4==3.
Todd Lehman
2

golflua 147 141

Hitungan di atas mengabaikan baris baru yang saya tambahkan untuk melihat fungsi yang berbeda. Meskipun desakan untuk tidak melakukannya, saya dengan brutal memecahkan bilangan prima dalam kasus.

\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())))

Mengembalikan 1 jika benar dan 0 jika tidak.

Versi Lua ungolfed,

-- 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))
Kyle Kanos
sumber
Anda dapat menyimpan 6 karakter dengan hanya menghubungkan tonumber(io.read())sebagai argumen gpada akhirnya, dan 2 lainnya dengan menghapus baris baru
mniip
@ mniip: baris baru tidak dihitung, saya baru saja menambahkannya untuk kejelasan (tidak ada bergulir ke samping). Saya akan memperbarui baca di g ketika saya mulai bekerja sedikit. Terima kasih!
Kyle Kanos
Nah apakah masih bekerja dalam waktu yang wajar untuk jumlah besar? Saya terutama berpikir tentang bruteforcing dalam cara memeriksa semua bilangan bulat gaussian di amana |a| <= |z|if a | z(jika amembagi z).
flawr
@ flawr: Saya mengujinya dengan a = 2147483644, b = 896234511 dan mendapat 0 sekitar 0,002 dtk. Saya juga mengujinya dengan 2147483629 & 2147483587 (dua bilangan prima sangat besar) dan mendapat 0 di 0,002 s lain. Saya mencoba untuk menemukan pasangan angka yang besar sehingga a ^ 2 + b ^ 2 adalah prima & memastikan bahwa saya punya solusi yang berfungsi untuk angka yang sedemikian besar.
Kyle Kanos
@ flawr: Diuji dengan a = 4600 & b = 5603 (a ^ 2 + b ^ 2 = 2147393609 adalah prima & <2 ^ 32-1) dan butuh 0,002 detik yang sama untuk mengembalikan 1. Yay!
Kyle Kanos
1

APL (NARS), 99 karakter, 198 byte

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}

uji:

  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  
RosLuP
sumber
1

Pesona Rahasia , 41 byte

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

Cobalah online!

Akhirnya menjadi jauh lebih mudah daripada yang saya pikirkan dan tidak banyak ruang untuk golf. Program asli yang saya blokir adalah:

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

Saya bermain-main dengan mencoba membandingkan kedua input pada saat yang sama (yang menyimpan semua 1 byte), tetapi ketika itu jatuh ke bagian "salah satu dari mereka adalah nol", tidak ada cara yang baik untuk mengetahui item mana yang bukan nol untuk melakukan pemeriksaan terakhir, apalagi cara untuk melakukannya tanpa menghabiskan setidaknya 1 byte (tidak ada penghematan keseluruhan).

Draco tidak lagi percaya pada SE
sumber
1

Mathematica, 149 Karakter

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}]

Kode tidak menggunakan fitur bilangan prima standar dari Mathematica, melainkan menghitung jumlah bilangan bulat dalam daftar {n / 1, n / 2, ..., n / n}; jika angkanya 1 atau 2, maka n adalah bilangan prima. Bentuk fungsi yang rumit:

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

Plot bonus dari semua Gaussian Primes mulai -20 hingga 20:

Plot bilangan prima gaussian

Italia
sumber
1

Ruby -rprime , 65 60 80 byte

Tidak memperhatikan aturan "tidak dapat menggunakan 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}

Cobalah online!

Nilai Tinta
sumber
0

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
Falko
sumber
Karena 3 adalah nomor terbesar yang dapat menjadi mod 4, Anda dapat mengganti ==3dengan>2
FlipTack