Tugas
Tulis fungsi yang menerima dua bilangan bulat a,b
yang mewakili bilangan bulat Gaussian z = a+ib
( bilangan kompleks). Program ini harus kembali benar atau salah tergantung pada apakah a+ib
merupakan perdana Gaussian atau tidak .
Definisi:
a + bi
adalah Gaussian prime jika dan hanya jika memenuhi salah satu dari kondisi berikut:
a
danb
keduanya bukan nol dana^2 + b^2
primaa
adalah nol,|b|
prima dan|b| = 3 (mod 4)
b
adalah 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 isprime
atau prime_list
atau nthprime
atau factor
. Jumlah byte terendah menang. Program harus bekerja di a,b
mana a^2+b^2
bilangan 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):
Beberapa bilangan prima yang lebih besar:
(9940, 43833)
(4190, 42741)
(9557, 41412)
(1437, 44090)
sumber
factor
di Bash,mf
danmF
di CJam, ...)Jawaban:
Haskell - 77/
108107 Karakterpenggunaan: di kedua solusi, mengetikkan% b akan mengembalikan apakah + bi adalah prime gaussian.
terendah yang saya kelola, tetapi tidak ada kreativitas atau kinerja (77 karakter)
solusi ini hanya menjalankan semua angka di bawah n untuk memeriksa apakah itu prima.
versi tanpa ungolfed:
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)
versi tanpa ungolfed:
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.
sumber
C,
149118 karakterVersi yang diedit (118 karakter):
Ini adalah fungsi tunggal:
Ini melipat uji bilangan bulat integer menjadi ekspresi
n/d/d|n<2
tersembunyi dalam perhitungan nilai kembali. Kode golf ini juga digunakana*b
sebagai penggantia&&b
(dengan kata laina!=0 && b!=0
) dan trik lain yang melibatkan operator diutamakan dan pembagian bilangan bulat. Sebagai contohn/d/d
adalah cara yang lebih singkat untuk mengatakann/d/d>=1
, yang merupakan cara yang aman untuk mengatakann>=d*d
ataud*d<=n
atau pada dasarnyad<=sqrt(n)
.Versi asli (149 karakter):
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:
sumber
d++
tidak terjadi sebagai bagian dari kondisi, selain itu mengacaukan logika berikut. Juga, menggerakkan bagiand=2
dalamfor
loop sebenarnya meningkatkan jumlah karakter daripada menguranginya, karenad
masih perlu dinyatakan sebagaiint
sebelumfor
loop. Apakah saya melewatkan sesuatu?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.APL (Dyalog Unicode) ,
36474849474328 byteMengambil array dua bilangan bulat
a b
dan mengembalikan nilai Boolean pernyataana+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_false
alih-alihif_true⊣⍣condition⊢if_false
. -15 byte berkat ngn karena menemukan cara yang sama sekali berbeda untuk menulis kondisi-jika-selain sebagai kereta penuh.Cobalah online!
Penjelasan
sumber
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.
Aktifkan sebagai
ghci ./gprimes.hs
dan kemudian Anda dapat menggunakannya di shell interaktif. Catatan: angka negatif rewel dan harus ditempatkan dalam tanda kurung. Yaitusumber
Python -
121120 karakterp
memeriksa apakahabs(x)
prime dengan mengulangi semua angka dari 2 hinggaabs(x)**.5
(yangsqrt(abs(x))
). Ia melakukannya dengan menghasilkanx % s
untuk masing-masings
.all
kemudian memeriksa apakah semua nilai yang dihasilkan adalah nol dan berhenti menghasilkan nilai setelah bertemu dengan pembagix
. Dalamf
,f(b,a)
menggantikan kasing untukb==0
, terinspirasi oleh @killmous 'jawaban Haskell.-1 char dan perbaikan bug dari @PeterTaylor
sumber
s<abs(x)**.5
dengans*s<abs(x)
untuk menghemat 2. Meskipun Anda benar-benar harus memeriksa<=
, jadi mungkin bermasalah saat ini.f(0,15)
hasilTypeError: unsupported operand type(s) for &: 'bool' and 'generator'
dengan juru bahasa saya. :(f(0,15)
memberiFalse
untuk saya, baik pada 2.7.6 dan 3.4.1 (pada OS X). Anda versi apa?Python 2.7 ,
341301253 byte, dioptimalkan untuk kecepatanCobalah online!
Terima kasih: 40 +48 - seluruh bermain golf untuk Jo King
sumber
f
lambda juga uneccesary, bersama denganlist
panggilan. 257 byte tanpa itu, ditambah beberapa penghapusan spasi putih. Ini mungkin tidak seefisien lagiPerl -
110107105 karakterSaya harap saya mengikuti definisi yang ditautkan dengan benar ...
Tidak Disatukan:
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$n
bilangan prima dengan menghitung berapa angka antara 2 dan itu sendiri membaginya tanpa sisa (itugrep...<2
bagiannya), 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.sumber
$a%4>2
alih-alih$a%4==3
.golflua
147141Hitungan 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.
Mengembalikan 1 jika benar dan 0 jika tidak.
Versi Lua ungolfed,
sumber
tonumber(io.read())
sebagai argumeng
pada akhirnya, dan 2 lainnya dengan menghapus baris barua
mana|a| <= |z|
ifa | z
(jikaa
membagiz
).APL (NARS), 99 karakter, 198 byte
uji:
sumber
Pesona Rahasia , 41 byte
Cobalah online!
Akhirnya menjadi jauh lebih mudah daripada yang saya pikirkan dan tidak banyak ruang untuk golf. Program asli yang saya blokir adalah:
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).
sumber
Mathematica, 149 Karakter
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:
Plot bonus dari semua Gaussian Primes mulai -20 hingga 20:
sumber
Ruby
-rprime
,656080 byteTidak memperhatikan aturan "tidak dapat menggunakan isPrime" ...
Cobalah online!
sumber
Python -
117 122121sumber
==3
dengan>2