Ini adalah pertanyaan golf kode pertama saya, dan sangat sederhana, jadi saya minta maaf sebelumnya jika saya mungkin telah melanggar pedoman komunitas.
Tugasnya adalah mencetak, dalam urutan menaik, semua bilangan prima kurang dari satu juta. Format output harus satu angka per baris output.
Tujuannya, seperti pada kebanyakan pengiriman kode golf, adalah untuk meminimalkan ukuran kode. Mengoptimalkan runtime juga merupakan bonus, tetapi merupakan tujuan sekunder.
code-golf
kolmogorov-complexity
primes
Delan Azabani
sumber
sumber
10^6
bahkan lebih pendek;)1e6
:-DJawaban:
Mathematica ,
1724Hanya untuk perbandingan:
Seperti disebutkan dalam komentar saya gagal memberikan satu prime per baris; koreksi:
sumber
Prime~Array~78498
juga 17 :)Print/@
dan terminasi dengan;
untuk mencegah keluaran dari daftar panjangNull
perbaikan yang, dengan biaya 8 karakter tambahan.Python 3, 46 byte
Pada saat loop mencapai pengujian
k
, iteratif menghitung faktor kuadratP=(k-1)!^2
. Jikak
prima, maka itu tidak muncul dalam produk1 * 2 * ... * (k-1)
, jadi itu bukan faktorP
. Tapi, jika itu komposit, semua faktor utamanya lebih kecil dan begitu juga dalam produk. Kuadrat sebenarnya hanya diperlukan untuk berhentik=4
dari salah disebut prima.Lebih kuat lagi, teorema Wilson menyatakan bahwa ketika
k
prima,P%k
sama dengan1
. Meskipun kita hanya perlu bukan nol di sini, ini berguna secara umum yangP%k
merupakan variabel indikator untuk apakahk
prime.sumber
C, 61 karakter
Hampir persis sama dengan yang ini (pertanyaannya juga hampir sama persis).
sumber
SEG-FAULT
setelah mencetak881
-O3
untukgcc
menyelesaikan masalah !!n=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:m-++n%m);}
MATLAB
(16)(12)Sayangnya, ini menghasilkan satu baris:
tapi itu diselesaikan dengan transpose matriks sederhana:
dan saya dapat memotong beberapa karakter dengan menggunakan notasi eksponensial (seperti yang disarankan dalam komentar):
sumber
1e6
bukannya1000000
membantu di sini juga.'
di akhirBash (37 karakter)
(60 karakter)
di komputer saya (cpu 2,0 GHz, ram 2 GB) membutuhkan waktu 14 detik.
sumber
seq 2 1000000|factor|sed 's/[0-9]*: //g;/^.* .*$/ d'
seq 1e6|factor|awk '$0=$2*!$3'
sedikit lebih pendek.c p
mana c adalah symlink ke cat dan p adalah file teks dengan bilangan prima hingga satu juta ... dapatkah Anda melakukannya dengan builtin shell?seq
danfactor
berada dicoreutils
, jadi itu sah.sed
juga cukup di mana-mana.coreutils
dapat diperlakukan seperti built-in. Bash tanpa coreutils seperti C ++ tanpa STL.J, 21 karakter
yang dapat disingkat menjadi
jika Anda tahu berapa banyak bilangan prima ada di bawah 10.00000.
sumber
,.
,, alih-alih 1 [\\ untuk menyimpan karakter. Lepaskan kurung yang tidak perlu, dan menggunakan notasi eksponensial:1e6
.,.i.&.(p:^:_1)1e6
Tidak lebih pendek (setelah menerapkan saran @ Umar) tapi saya menemukan penggunaan di bawah menarik.PowerShell,
4744 byteSangat lambat, tapi yang terpendek yang bisa saya lakukan.
PowerShell, 123 byte
Ini jauh lebih cepat; jauh dari optimal, tetapi kompromi yang baik antara efisiensi dan singkatnya.
sumber
Ruby 34
sumber
Bash, 30 byte
Karena saeedn tidak akan bertindak atas saran saya - yang lebih pendek dan lebih cepat daripada pendekatannya - saya pikir saya akan memposting jawaban saya sendiri:
Bagaimana itu bekerja
daftar semua bilangan bulat positif hingga 1.000.000.
faktor mereka satu per satu. Untuk sepuluh pertama, hasilnya adalah sebagai berikut:
Akhirnya,
mengubah seluruh baris (
$0
) ke produk dari bidang kedua (faktor prima pertama) dan negasi logis dari bidang ketiga (1
jika merupakan satu faktor prima atau kurang,0
jika tidak).Ini menggantikan garis yang sesuai dengan bilangan prima dengan angka itu sendiri dan semua garis lainnya dengan nol. Karena awk hanya mencetak nilai kebenaran, hanya bilangan prima yang akan dicetak.
sumber
awk '$0=$2*!$3'
sangat keren!Ruby
5041sumber
.to_a
, karena Enumerable sudah termasukselect
. Anda juga dapat menggunakan notasi steno untuk Simbol # to_proc untuk mempersingkat lebih lanjut:p (2..1e6).select &:prime?
(1 bukan prime)require'prime';p Prime.take 78498
.Bash, 37
Akan bermain golf lebih banyak, jika aku bisa ...
Sebagian besar dari ini mencoba mem
factor
- parsing format output yang canggung.Butuh 5,7 detik untuk menyelesaikannya di mesin saya.
(Kebetulan posting saya adalah yang pertama masuk pada halaman kedua jawaban, jadi tidak ada yang akan melihatnya ...)
Solusi lama
Ini lebih lama dan lebih lambat (butuh 10 detik).
sumber
factor
sebelumnya, tetapi ada di sana di coreutils!seq 1e6|factor|grep -oP "(?<=: )\d+$"
with perl-grep lookbehind-P
memungkinkan regex gaya-perl.(?<=: )
adalah tampilan positif di balik string ":". Pada dasarnya ini mengatakan bahwa ":" harus datang sebelum pertandingan apa\d+$
, tetapi sebenarnya bukan bagian dari pertandingan, jadi-o
opsi hanya memberi kita satu angka yang cocok setelah titik dua, yaitu hanya memberikan angka di mana hanya ada satu faktor, yaitu prima.Python 3.x: 66 karakter
Solusi yang lebih efisien: 87 karakter
Berdasarkan Saringan Eratosthenes.
sumber
0
dan1
. Anda dapat memperbaikinya dengan menggunakanrange(2,10**6)
. Juga, saya pikirif
pernyataan itu harus berada di jalur yang terpisah dari luarfor
atau Anda mendapatkan kesalahan.Haskell, 51
sumber
mapM_
kemapM
, nilai pengembalian tidak akan dicetak, dan ini adalah Code Golf. ;)APL, 15
Penerjemah saya mengalami masalah memori, tetapi itu bekerja secara teori.
sumber
⍪
di depan untuk membuat satu angka per baris, dan Anda tidak memerlukannya,
.⍳
adalah bilangan bulat pertama.1↓
menjatuhkan yang pertama.p←
ditugaskan ke hal.p∘.×p
membuat tabel perkalian.p~
menghapus dari p apa pun yang ada di kanan. (,
tidak diperlukan, itu mencungkil tabel ke dalam daftar.)Perl, 49 byte
Ekspresi reguler kung fu :)
Versi tidak disatukan:
Bahkan belum membuat kemajuan 10% saat saya mengetik posting ini!
Sumber untuk regex: http://montreal.pm.org/tech/neil_kandalgaonkar.shtml
sumber
1000000
dapat ditulis10**6
Julia, 11
Sepertinya built in semakin upvotes, ditambah saya membutuhkan lebih banyak kata untuk jawaban yang lebih lama.
sumber
J (15 atau 9)
Saya tidak percaya ini mengalahkan Mathematica (bahkan jika itu hanya
satuper 2 karakter)Atau:
sumber
... The output format should be one number per line of output.
Itu sebabnya jawaban saya dimulai dengan1[\
.gs2, 5 byte
Dikodekan dalam CP437:
1C 29
mendorong satu juta,11 6C
adalah bilangan prima di bawah ini,54
adalah menunjukkan garis.sumber
GolfScript, 22/20 (20/19) byte
Dengan mengorbankan kecepatan, kode dapat dibuat dua byte lebih pendek:
Jika format output yang ditentukan dalam pertanyaan yang diedit diabaikan (yang merupakan jawaban dari banyak jawaban yang ada), dua byte dapat disimpan dalam versi cepat dan satu dapat disimpan dalam versi lambat:
Ini akan mencetak LF tambahan setelah bilangan prima untuk versi cepat, dan itu akan mencetak bilangan prima sebagai larik untuk yang lambat.
Bagaimana itu bekerja
Kedua versi ini merupakan implementasi dari saringan Eratosthenes .
Versi cepat melakukan hal berikut:
Atur
A = [ 2 3 4 … 999,999 ]
dan| = [ 0 1 2 … 999,999 ]
.Atur
N = A[0]
dan cetakN
.Kumpulkan setiap elemen ke-N dari
|
dalamC
. Ini adalah kelipatan dariN
.Setel
A = A - C
.Jika
A
tidak kosong, kembali ke 2.Versi lambat bekerja dengan cara yang sama, tetapi alih-alih menghapus kelipatan minimum "A" (yang selalu prima), ia menghapus kelipatan semua bilangan bulat positif di bawah 1.000.000.
Daya saing
Dengan tidak adanya fungsi matematika bawaan untuk memfaktisasi atau memeriksa primality, semua solusi GolfScript akan sangat besar atau sangat tidak efisien.
Meskipun masih jauh dari efisien, saya pikir saya telah mencapai rasio kecepatan-ke-ukuran yang layak. Pada saat pengajuannya, pendekatan ini tampaknya menjadi yang terpendek dari mereka yang tidak menggunakan salah satu built-in yang disebutkan di atas. Saya katakan sepertinya karena saya tidak tahu bagaimana beberapa jawaban bekerja ...
Saya telah membandingkan keempat solusi GolfScript yang diajukan: w0lf's (divisi percobaan), jawaban saya yang lain (teorema Wilson) dan dua jawaban ini. Inilah hasilnya:
sumber
NARS2000 APL, 7 karakter
sumber
Golfscript
26 2524Sunting (satu arang tersimpan lagi berkat Peter Taylor):
Kode lama:
Kode ini hanya memiliki nilai teoritis, karena sangat lambat dan tidak efisien. Saya pikir itu bisa memakan waktu berjam-jam untuk berjalan.
Jika Anda ingin mengujinya, coba misalnya hanya bilangan prima hingga 100:
sumber
\;
dengan*
. (Anda juga bisa mendapatkan lebih cepat untuk penghitungan karakter saat ini dengan menemukan pembagi pertama daripada semuanya:10 6?,2>{.),2>{1$\%!}?=},`
.,
dengan:x,
dan\.@
denganx\
(spasi putih adalah karena melarikan diri masalah dengan MD dalam komentar) dan menghapus*
.CJam - 11
1e6,
- array 0 ... 999999{mp},
- pilih bilangan primaN*
- gabung dengan baris barusumber
GolfScript, 25 (24) byte
Jika format output yang ditentukan dalam pertanyaan yang diedit diabaikan, satu byte dapat disimpan:
Ini akan mencetak bilangan prima sebagai array (seperti banyak solusi lain lakukan) daripada satu per baris.
Bagaimana itu bekerja
Gagasan umum adalah menggunakan teorema Wilson , yang menyatakan bahwa n > 1 adalah prima jika dan hanya jika
Tolak ukur
Lebih cepat dari pembagian percobaan, tetapi lebih lambat dari ayakan Eratosthenes. Lihat jawaban saya yang lain .
sumber
Java, 110 byte
Menggunakan pembagian unary melalui regex sebagai tes primality.
sumber
C,
9188858281807672 karakterAlgoritma ini sangat tidak efisien, tetapi karena kita melakukan golf kode yang seharusnya tidak masalah.
sumber
main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;}
atau beberapa ide seperti ini (karena saya sebenarnya tidak mengkompilasinya)i
menjadi 0? Saya pikir, jika Anda memberikan setiap argumen, itu akan gagal. Juga, saya pikirj
akan memiliki semacam kesalahan tipe. Tapi tidak yakinb
.Mathematica 25
Dengan asumsi Anda tidak tahu jumlah bilangan prima kurang dari 10 ^ 6:
sumber
J, 16 karakter
Tanpa persyaratan format output, ini dapat dikurangi menjadi 13 karakter:
1]\
hanya mengambil array peringkat 1 dari bilangan prima, mengubahnya menjadi array peringkat 2, dan menempatkan setiap prime pada barisnya sendiri - sehingga format output default interpreter mengubah daftar satu baris menjadi satu prima per baris.(#~ f) y
pada dasarnyafilter
, di manaf
mengembalikan boolean untuk setiap elemen dalamy
.i.1e6
adalah kisaran bilangan bulat [0,1000000), dan1&p:
merupakan fungsi boolean yang mengembalikan 1 untuk bilangan prima.sumber
R,
4543 karakterUntuk setiap angka x dari 2 hingga 1e6, cukup keluarkan jika jumlah x mod 2 hingga x yang sama dengan 0 kurang dari 2.
sumber
Bash (433643)
Upaya saya (tidak begitu pintar) adalah menggunakan faktor untuk faktor produk.
Sayangnya dengan jumlah besar produknya tentu saja besar. Butuh waktu lebih dari 12 jam untuk berlari. Saya memutuskan untuk mempostingnya karena saya pikir itu unik.
Ini kode lengkapnya.
Jika bilangan prima di bawah enam itu akan masuk akal.
Oh well, saya sudah mencoba.
sumber
factor
jauh lebih buruk daripada algoritma pembagian percobaan dasar.C #, 70
Anda tidak akan melihat banyak di sini meskipun untuk waktu yang lama ...
sumber
double
1e6
keint
, tetapiint
diharuskan olehRange
. (2) BatinRange
harus paling tidak meneriman-2
syarat, jika tidak Anda akan mengujin % n
yang jelas0
. (3) Anda menulisx%n
kapan pun Anda maun%x
. Memperbaiki masalah ini, sesuatu seperti ini akan berfungsi:Enumerable.Range(2,999999).Where(n=>Enumerable.Range(2,n-2).All(x=>n%x!=0))
Namun, ini masih tidak menghasilkan angka; persyaratannya satu per baris.