Aturannya sederhana:
- Pertama n bilangan prima (bukan bilangan prima di bawah n ), harus dicetak ke output standar dipisahkan oleh baris baru (bilangan prima harus dihasilkan dalam kode)
- bilangan prima tidak dapat dihasilkan oleh fungsi inbuilt atau melalui perpustakaan , yaitu penggunaan fungsi inbuilt atau perpustakaan seperti, prime = get_nth_prime (n), is_a_prime (angka), atau daftar faktor = list_all_factors (angka) tidak akan sangat kreatif.
Penilaian - Katakanlah, kita mendefinisikan Skor = f ([jumlah karakter dalam kode]), O ( f (n)) menjadi kompleksitas algoritme Anda di mana n adalah jumlah bilangan prima yang ditemukannya. Jadi misalnya, jika Anda memiliki 300 kode char dengan kompleksitas O (n ^ 2), skor adalah 300 ^ 2 = 90000 , untuk 300 karakter dengan O (n * ln (n)), skor menjadi 300 * 5.7 = 1711.13 ( mari kita anggap semua log menjadi log natural untuk kesederhanaan)
Gunakan bahasa pemrograman yang ada, kemenangan skor terendah
Sunting: Masalah telah diubah dari menemukan 'prima pertama 1000000' menjadi 'n primes pertama' karena kebingungan tentang apa 'n' di O (f (n)) adalah, n adalah jumlah bilangan prima yang Anda temukan (menemukan bilangan prima adalah masalah di sini dan kompleksitas masalah tergantung pada jumlah bilangan prima yang ditemukan)
Catatan: untuk memperjelas beberapa kebingungan tentang kompleksitas, jika 'n' adalah jumlah bilangan prima yang Anda temukan dan 'N' adalah bilangan prima ke-n, kompleksitas dalam n adalah dan N tidak setara yaitu O (f (n))! = O (f (N)) sebagai, f (N)! = Konstan * f (n) dan N! = Konstan * n, karena kita tahu bahwa fungsi utama ke-n tidak linier, saya pikir karena kami menemukan 'n' Kompleksitas bilangan prima harus mudah diungkapkan dalam hal 'n'.
Seperti yang ditunjukkan oleh Kibbee, Anda dapat mengunjungi situs ini untuk memverifikasi solusi Anda (di sini , adalah daftar google docs lama)
Harap Sertakan ini dalam solusi Anda -
kompleksitas apa yang dimiliki program Anda (termasuk analisis dasar jika tidak sepele)
panjang kode karakter
skor akhir yang dihitung
Ini adalah Pertanyaan CodeGolf pertama saya, jadi, jika ada kesalahan atau celah dalam aturan di atas, mohon tunjukkan.
sumber
1[\p:i.78498
jawaban saya untuk ini1[\p:i.1000000
. Bahkan dengan asumsi bahwa algoritma prime internal J adalah O (n ^ 2) skor saya masih hanya 196.n
jumlah bilangan prima atau bilangan prima maksimum, dan semua orang mengabaikan fakta bahwa penambahan bilangan dalam kisaran0..n
ituO(logn)
, dan penggandaan dan pembagian bahkan lebih mahal. Saya menyarankan Anda memberikan beberapa contoh algoritma beserta kompleksitasnya yang benar.O-tilde(k^6)
. Ini mengarah pada implikasi bahwa siapa pun yang mengklaim waktu berjalan lebih baik daripadaO-tilde(n ln n (ln(n ln n))^6)
salah paham beberapa bagian dari masalah; dan untuk pertanyaan bagaimanaO-tilde
kompleksitas harus ditangani dalam penilaian.Jawaban:
Python (129 karakter, O (n * log log n), skor 203.948)
Saya akan mengatakan Saringan Eratosthenes adalah cara untuk pergi. Sangat sederhana dan relatif cepat.
Kode ditingkatkan dari sebelumnya.
Python (
191 156152 karakter, O (n * log log n) (?), Skor 252.620 (?))Saya tidak bisa menghitung kompleksitas sama sekali, ini adalah perkiraan terbaik yang bisa saya berikan.
n*int(l(n)+l(l(n)))
adalah batas atas darin
bilangan prima th.sumber
n
tetapi tidak pada jumlah bilangan prima. Jadi, saya menganggap skor harus lebih tinggi. Lihat komentar saya di atas.n
? Apa itu?N=15485864
. Untuk perhitungan kompleksitas berdasarkann=1000000
, Anda dapat mengatakanN=n*log(n)
(karena kepadatan bilangan prima).Haskell, n ^ 1,1 tingkat pertumbuhan empiris, 89 karakter, skor 139 (?)
Berikut ini berfungsi di GHCi prompt ketika perpustakaan umum yang digunakan sudah dimuat sebelumnya. Cetak n th prima, 1 berbasis:
let s=3:minus[5,7..](unionAll[[p*p,p*p+2*p..]|p<-s])in getLine>>=(print.((0:2:s)!!).read)
Ini adalah saringan Eratosthenes tanpa batas, menggunakan pustaka penggunaan umum untuk daftar yang dipesan. Kompleksitas empiris antara 100.000 dan 200.000 bilangan prima
O(n^1.1)
. Cocok untukO(n*log(n)*log(log n))
.Tentang estimasi kompleksitas
Saya mengukur waktu berjalan untuk 100k dan 200k bilangan prima, kemudian dihitung
logBase 2 (t2/t1)
, yang menghasilkann^1.09
. Menentukang n = n*log n*log(log n)
, menghitunglogBase 2 (g 200000 / g 100000)
memberin^1.12
.Lalu
89**1.1 = 139
, meskipung(89) = 600
. --- (?)Tampaknya untuk penilaian laju pertumbuhan diperkirakan harus digunakan alih-alih fungsi kompleksitas itu sendiri. Misalnya,
g2 n = n*((log n)**2)*log(log n)
jauh lebih baik daripadan**1.5
, tetapi untuk 100 karakter keduanya menghasilkan skor3239
dan1000
, masing-masing. Ini tidak mungkin benar. Estimasi pada kisaran 200k / 100k memberilogBase 2 (g2 200000 / g2 100000) = 1.2
dan dengan demikian skor100**1.2 = 251
.Juga, saya tidak berusaha mencetak semua bilangan prima, hanya n perdana ke- saja.
Tanpa impor, 240 karakter. n ^ 1,15 tingkat pertumbuhan empiris, skor 546.
sumber
Haskell,
7289 karakter, O (n ^ 2), Skor 7921Skor tertinggi per hitungan char menang benar? Dimodifikasi untuk yang pertama N. Juga saya tampaknya tidak dapat menggunakan kalkulator, jadi skor saya tidak seburuk yang saya kira. (menggunakan kompleksitas untuk pembagian percobaan dasar seperti yang ditemukan dalam sumber di bawah).
Per Will Ness di bawah ini bukanlah program Haskell penuh (itu sebenarnya bergantung pada REPL). Berikut ini adalah program yang lebih lengkap dengan pseudo-saringan (impor sebenarnya menyimpan char, tapi saya tidak suka impor dalam kode golf).
Versi ini tidak diragukan lagi (n ^ 2). Algoritma ini hanya versi golf dari naif `` saringan '', seperti yang terlihat di sini Old ghci 1 kapal
Meninggalkan jawaban yang lama dan curang karena perpustakaan yang ditautkannya cukup bagus.
Lihat di sini untuk implementasi dan tautan untuk kompleksitas waktu. Sayangnya roda memiliki waktu pencarian log (n), memperlambat kita oleh faktor.
sumber
C #, 447 Karakter, Bytes 452, Skor?
Varian scriptcs, 381 Karakter, 385 Bytes, Nilai?
Jika Anda menginstal skrip maka Anda dapat menjalankannya.
PS Saya menulis ini di Vim
:D
sumber
=
dan<
. Juga, saya tidak berpikir ada perbedaan dalam byte dan karakter untuk kode ini - itu 548 karakter dan 548 byte.GolfScript (45 karakter, skor diklaim ~ 7708)
Ini melakukan pembagian percobaan sederhana oleh bilangan prima. Jika mendekati ujung tombak dari Ruby (yaitu menggunakan 1.9.3.0) aritmatika menggunakan perkalian Toom-Cook 3, jadi divisi percobaan adalah O (n ^ 1.465) dan biaya keseluruhan divisi adalah
O((n ln n)^1.5 ln (n ln n)^0.465) = O(n^1.5 (ln n)^1.965)
†. Namun, dalam GolfScript menambahkan elemen ke array membutuhkan menyalin array. Saya telah mengoptimalkan ini untuk menyalin daftar bilangan prima hanya ketika menemukan bilangan prima baru, sehingga hanyan
total kali. Setiap operasi penyalinan adalahO(n)
item dengan ukuranO(ln(n ln n)) = O(ln n)
†, memberiO(n^2 ln n)
.Dan inilah, anak laki-laki dan perempuan, mengapa GolfScript digunakan untuk bermain golf daripada untuk pemrograman serius.
†
O(ln (n ln n)) = O(ln n + ln ln n) = O(ln n)
. Saya seharusnya melihat ini sebelum mengomentari berbagai posting ...sumber
Ini sangat mudah bahkan editor teks saya dapat melakukan ini!
Vim: 143 penekanan tombol (115 tindakan): O (n ^ 2 * log (n)): Nilai: 101485.21
Pengajuan:
Input: N harus di baris pertama dari dokumen kosong. Setelah ini selesai, setiap prime dari 2 ke N akan menjadi baris terpisah.
Menjalankan Perintah:
Pertama, perhatikan bahwa setiap perintah dengan tanda sisipan di depannya berarti Anda harus menahan Ctrl dan mengetik huruf berikutnya (mis. ^ V is Ctrl-vdan ^ R isCtrl-r ).
Ini akan menimpa apa pun di register @a, @b, @d, dan @p Anda.
Karena ini menggunakan qperintah, itu tidak bisa hanya ditempatkan di makro. Namun, berikut adalah beberapa tips untuk menjalankannya.
qpqqdq
hanya membersihkan registerA^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"dd
akan membuat daftar angka 2 hingga N +1. Ini adalah jeda antara dua bagian utama, jadi setelah ini selesai, Anda tidak perlu melakukannya lagimpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qqpmp"aywgg@dqgg@p
tidak perlu diketik sekaligus. Cobalah untuk menghindari backspace karena dapat mengacaukan sesuatu.qdqqpq
kemudian coba baris ini lagi.Untuk N besar, ini sangat lambat. Butuh sekitar 27 menit untuk menjalankan N = 5000; anggap dirimu sudah diperingatkan.
Algoritma:
Ini menggunakan algoritma rekursif dasar untuk menemukan bilangan prima. Diberikan daftar semua bilangan prima antara 1 dan A, A + 1 adalah bilangan prima jika tidak dapat dibagi dengan angka-angka dalam daftar bilangan prima. Mulai dari A = 2 dan tambahkan bilangan prima ke daftar saat ditemukan. Setelah N rekursi, daftar akan berisi semua bilangan prima hingga N.
Kompleksitas
Algoritma ini memiliki kompleksitas O (nN), di mana N adalah nomor input dan n adalah jumlah bilangan prima hingga N. Setiap rekursi menguji n angka, dan rekursi N dilakukan, menghasilkan O (nN).
Namun, N ~ n * log (n), memberikan kompleksitas akhir sebagai O (n 2 * log (n)) ( https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number )
Penjelasan
Tidak mudah membedakan aliran program dari perintah vim, jadi saya menulis ulang dengan Python mengikuti aliran yang sama. Seperti kode Vim, kode python akan error ketika mencapai akhir. Python tidak suka terlalu banyak rekursi; jika Anda mencoba kode ini dengan N> 150 atau lebih, itu akan mencapai kedalaman rekursi maksimum
Sekarang, untuk memecah penekanan tombol yang sebenarnya!
qpqqdq
Menghapus register @d dan @p. Ini akan memastikan tidak ada yang berjalan saat mengatur makro rekursif ini.A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"dd
Mengubah input menjadi daftar angka dari 2 menjadi N + 1. Entri N +1 dihapus sebagai efek samping dari pengaturan makro @d.mpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0q
menulis makro @d, yang mengimplementasikan fungsi d () di atas. Pernyataan "Jika" menarik untuk diterapkan di Vim. Dengan menggunakan operator pencarian *, dimungkinkan untuk memilih jalur tertentu untuk diikuti. Memecah perintah lebih jauh kita dapatkanmpqd
Tetapkan tanda p di sini dan mulai merekam @d makro. Tanda p perlu diatur sehingga ada titik yang diketahui untuk melompat saat ini berjalano^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>
Menulis teks pernyataan if / else0*w*wyiWdd@0
sebenarnya mengeksekusi pernyataan if.@a @b 0 0 `pj@p @a 0 (@a%@b) `pdd@p 0 `dj@d
0
memindahkan kursor ke awal baris*w*w
Memindahkan kursor ke kode yang akan dieksekusi berikutnya`pj@p
, yang bergerak ke nomor berikutnya untuk @a dan menjalankan @p di atasnya.`pdd@p
, yang menghapus angka saat ini @a, kemudian jalankan @p pada yang berikutnya.`dj@d
, yang memeriksa angka berikutnya untuk @b untuk melihat apakah itu adalah faktor @ayiWdd@0
menarik perintah ke register 0, menghapus baris dan menjalankan perintahq
mengakhiri rekaman makro @dSaat ini pertama kali dijalankan,
`pdd@p
perintah dijalankan, menghapus baris N +1.qpmp"aywgg@dq
menulis @p makro, yang menyimpan nomor di bawah kursor, kemudian pergi ke entri pertama dan menjalankan @d pada itu.gg@p
sebenarnya mengeksekusi @p sehingga akan mengulangi seluruh file.sumber
QBASIC, 98 Chars, Complexity N Sqrt (N), Score 970
sumber
IF K=
(jadi panjang program tidak termasuk angka). Seperti berdiri, program ini mencetak n primes pertama tidak termasuk 2, yang dapat diperbaiki dengan menambahkan?2
di awal, dan mengubahK=...
keK=...-1
. Program ini juga dapat golfed sedikit dengan mengambil ruang dariJ=2 TO
,J=0 THEN
,K=...-1 THEN
, dan dengan menghapus Indentasi tersebut. Saya percaya ini menghasilkan program 96 karakter.Scala 263 karakter
Diperbarui agar sesuai dengan persyaratan baru. 25% dari kesepakatan kode dengan menemukan batas atas yang wajar untuk menghitung bilangan prima di bawah ini.
Saya juga mendapat ayakan.
Berikut ini adalah uji empiris dari biaya perhitungan, yang tidak dianalisa untuk analisis:
mengarah ke penghitungan berikut:
Saya tidak yakin bagaimana cara menghitung skor. Apakah layak untuk menulis 5 karakter lagi?
Untuk yang lebih besar dan mengurangi perhitungan sekitar 16% dalam kisaran itu, tetapi afaik untuk rumus skor, kita tidak mempertimbangkan faktor konstan?
Pertimbangan Big-O baru:
Untuk menemukan 1 000, 10 000, 100 000 bilangan prima dan seterusnya, saya menggunakan rumus tentang kepadatan bilangan prima x => (math.log (x) * x * 1.3 yang menentukan lingkaran luar yang saya jalankan.
Jadi untuk nilai i dalam 1 hingga 6 => NPrimes (10 ^ i) berjalan 9399, 133768 ... dikali loop luar.
Saya menemukan fungsi-O ini berulang dengan bantuan dari komentar Peter Taylor, yang menyarankan nilai eksponensial yang jauh lebih tinggi, daripada 1,01 ia menyarankan 1,5:
O: (n: Int) Panjang
ns: Daftar [Panjang] = Daftar (102, 4152, 91532, 1612894, 25192460, 364664351)
Ini adalah quotients, jika saya menggunakan 1.01 sebagai eksponen. Inilah yang konter temukan secara empiris:
Dua nilai pertama adalah outlier, karena saya telah membuat koreksi konstan untuk formulasi estimasi saya untuk nilai-nilai kecil (hingga 1000).
Dengan saran Peter Taylors 1,5, akan terlihat seperti:
Sekarang dengan nilai saya, saya dapat:
Tapi saya tidak yakin, seberapa dekat saya dengan fungsi-O saya dengan nilai-nilai yang diamati.
sumber
O(M^1.5 / ln M)
, dan setiap kali melalui Anda melakukanO(ln M)
pekerjaan (tambahan), jadi secara keseluruhan ituO(M^1.5) = O((n ln n)^1.5)
.def O(n:Int) = (math.pow((n * math.log (n)), 1.02)).toLong
saya lebih dekat ke nilai-nilai, secara empiris ditemukan dengan penghitung saya. Saya memasukkan temuan saya di posting saya.Ruby 66 chars, O (n ^ 2) Skor - 4356
lazy
tersedia sejak Ruby 2.0, dan1.0/0
merupakan trik keren untuk mendapatkan rentang tak terbatas:sumber
(2..(1.0/0)).lazy.select{|i|!(2...i).any?{|j|i%j<1}}.take(n).to_a
(2..(1.0/0)).lazy.select{|i|(2..i).one?{|j|i%j<1}}.take(n).to_a
. Ini memangkas dua karakter lagi.(2..(1.0/0)).lazy.select{|i|!(2...i).any?{|j|i%j<1}}.first(n)
akan menghasilkan 61 karakter.Ruby, 84 karakter, 84 byte, skor?
Yang ini mungkin agak terlalu pemula untuk bagian ini, tetapi saya bersenang-senang melakukannya. Itu hanya loop sampai
f
(bilangan prima ditemukan) sama dengann
, jumlah bilangan prima yang diinginkan dapat ditemukan.Bagian yang menyenangkan adalah bahwa untuk setiap loop itu menciptakan sebuah array dari 2 menjadi satu kurang dari jumlah yang diperiksa. Kemudian memetakan setiap elemen dalam array menjadi modulus dari angka asli dan elemen, dan memeriksa untuk melihat apakah ada hasilnya nol.
Juga, saya tidak tahu bagaimana mencetaknya.
Memperbarui
Kode dipadatkan dan menyertakan nilai (benar-benar arbitrer) untuk
n
Asli
The
i += 1
bit danuntil
lingkaran adalah semacam melompat keluar pada saya sebagai area untuk perbaikan, tapi di trek ini aku semacam terjebak. Bagaimanapun, itu menyenangkan untuk dipikirkan.sumber
Scala, 124 karakter
Divisi uji coba sederhana hingga akar kuadrat. Kompleksitas karena itu harus O (n ^ (1,5 + epsilon))
124 ^ 1,5 <1381, jadi itu nilai saya, saya kira?
sumber
Perl - 94 karakter, O (n log (n)) - Nilai: 427
Python - 113 karakter
sumber
AWK,
9686 byteTerjemahan: Lihat Bu! Hanya menambah dan beberapa pembukuan!
File
fsoe3.awk
:Menjalankan:
BASH, 133 byte
File
x.bash
:Menjalankan:
Bilangan prima dihitung dengan membiarkan bilangan prima yang sudah ditemukan melompat pada "pita bilangan bulat positif". Pada dasarnya ini adalah Saringan Of Eratosthenes.
... adalah algoritma yang sama dalam Python dan mencetak waktu ketika
l
-th prime ditemukan alih-alih prime itu sendiri.Output diplot dengan
gnuplot
hasil sebagai berikut:Lompatan mungkin ada hubungannya dengan keterlambatan file i / o karena menulis data buffer ke disk ...
Dengan menggunakan jumlah bilangan prima yang jauh lebih besar untuk menemukan, akan membawa penundaan tambahan yang bergantung pada sistem ke dalam gim, misalnya larik yang mewakili "pita bilangan bulat positif" tumbuh terus-menerus dan cepat atau lambat akan membuat setiap komputer meminta lebih banyak RAM (atau kemudian ditukar).
... jadi mendapatkan gagasan tentang kompleksitas dengan melihat data eksperimental tidak banyak membantu ... :-(
Sekarang menghitung penambahan yang dibutuhkan untuk menemukan
n
bilangan prima:sumber
Gnuplot
denganset term xterm
dan kemudian tangkapan layarxterm
jendela grafis (mungkin fitur yang hampir dilupakan). ;-)Scala 121 (99 tanpa boilerplate kelas Utama)
sumber
Python 3,
117106 byteSolusi ini sedikit sepele, karena menghasilkan 0 di mana bilangan tidak prima, tetapi saya tetap akan mempostingnya:
Juga, saya tidak yakin bagaimana menghitung kompleksitas suatu algoritma. Tolong jangan mundur karena ini. Sebaliknya, bersikap baik dan berkomentar bagaimana saya bisa menyelesaikannya. Juga, beri tahu saya bagaimana saya bisa mempersingkat ini.
sumber
print(i)
pada baris yang sama seperti untuk loop dan menghapus spasi diin [2]
,0 if
,0 in [i%j
dan+1,2)] else
.Haskell (52² = 2704)
sumber
Perl 6, 152 byte, O (n log n log (n log n) log (log (n log n))) (?), 9594,79 poin
Menurut halaman ini , kompleksitas bit untuk menemukan semua bilangan prima hingga n adalah O (n log n log log n); kompleksitas di atas menggunakan fakta bahwa nth prime sebanding dengan n log n.
sumber
Groovy (50 Bytes) - O (n * sqrt (n)) - Skor 353.553390593
Dimasukkan dalam n dan menampilkan semua angka dari 1 hingga n yang prima.
Algoritma yang saya pilih hanya keluaran primes n> 2, jadi menambahkan 1,2 di awal diperlukan.
Kerusakan
x%it
- Kejujuran tersirat jika tidak dapat dibagi, salah jika itu benar.(2..x**0.5).every{...}
- Untuk semua nilai antara 2 dan sqrt (x) memastikan bahwa mereka tidak dapat dibagi, untuk ini mengembalikan true, harus mengembalikan true untuk setiap .(1..it).findAll{x->...}
- Untuk semua nilai antara 1 dan n, temukan semua yang sesuai dengan kriteria tidak dapat dibagi antara 2 dan sqrt (n).{[1,2]+...}
- Tambahkan 1 dan 2, karena mereka selalu prima dan tidak pernah dicakup oleh algoritma.sumber
Racket 155 byte
Itu membuat daftar bilangan prima yang ditemukan dan memeriksa pembagian masing-masing nomor berikutnya dengan bilangan prima yang sudah ditemukan. Selain itu, ia memeriksa hanya sampai akar kuadrat dari angka yang diuji karena itu sudah cukup.
Tidak Disatukan:
Pengujian:
Keluaran:
sumber
awk 45 (kompleksitas N ^ 2)
lain
awk
, untuk primes hingga 100 digunakan seperti inikode golf bagian yang dihitung adalah
yang dapat dimasukkan ke dalam file skrip dan dijalankan sebagai
awk -f prime.awk <(seq 100)
sumber
Javascript, 61 karakter
Sedikit lebih buruk dari O (n ^ 2), akan kehabisan ruang stack untuk n besar.
sumber