Pertanyaan
Sebuah Sophie Germain utama adalah prima p sehingga 2p + 1 adalah prima juga. Misalnya, 11 adalah prime Sophie Germain karena 23 juga prima. Tulis program terpendek untuk menghitung bilangan prima Sophie Germain dalam urutan menaik
Aturan
- Bilangan prima Sophie Germain harus dihasilkan oleh program Anda , bukan dari sumber eksternal.
- Program Anda harus menghitung semua bilangan prima Sophie Germain di bawah 2³²-1
- Anda harus mencetak setiap Sophie Germain utama yang ditemukan program Anda.
- Orang dengan skor terendah menang
Mencetak gol
- 2 poin per byte kode Anda
- -10 jika Anda dapat menampilkan prime yang dihasilkan oleh program Anda lebih besar dari 2³²-1
code-challenge
primes
Meow Mix
sumber
sumber
Jawaban:
CJam
Untuk 17 karakter, kami mendapatkan penghitungan penuh hingga 2 ^ 32:
Untuk 4 karakter lebih, kami mendapatkan rentang yang cukup besar untuk menyertakan perdana SG yang lebih besar dari 2 ^ 32:
sejak 4294967681 = 2 ^ 32 + 385 <2 ^ 32 + 400.
Tentu saja, kami dapat memperluas rentang sama dengan gratis seperti
sumber
I,
memperlakukanI
sebagai integer 32-bit yang ditandatangani, sehingga nilai maksimumnyaI
adalah2 ** 31 - 1
.Pyth, 19 byte * 2 - 10 = 28
Perhatikan bahwa kompiler / pelaksana online tidak menampilkan keluaran karena ini merupakan loop tak terbatas.
Dijelaskan:
sumber
PZ
tidak mengembalikan nilai yang benar atau salah. Ini mengembalikan faktorisasi utamaZ
. Pengujian untuk prima adalah!tPZ
, yang memeriksa apakah faktorisasi prima hanya berisi satu faktor.!tP
kesalahan0
dan1
menjadi prima, karena faktorisasi prima mereka hanya berisi 1 faktor. Perbaikan mudah adalah dengan mengganti semuaZ
denganK
dan menetapkanK2
di awal.K1
alih-alihK2
, dan tukarkan jika dan kenaikannya. Dengan cara ini Anda dapat menghapus)
. Dan+1*K2
sama halnya denganhyK
.Pyth - 2 * 16 byte - 10 = 22
Menggunakan metode pemeriksaan perdana prima di Pyth dengan
!tP
dan menerapkannya baik untuk nomor dan safe-prime, dengan sedikit trik untuk memeriksa keduanya sekaligus. Naik10^10
, jadi saya akan mendapatkan bonus.Penjelasan segera hadir.Coba di bawah 1000 online .
sumber
sumber
CJam, 34 (2 * 22 - 10)
Mencetak semua bilangan prima Sophie Germain di bawah
12 ** 9
, yang mencakup4294967681 > 2 ** 32
.Saya memperkirakan bahwa ini akan memakan waktu sekitar 8 jam pada mesin saya. Saya akan menjalankannya malam ini.
sumber
Haskell, 2 * 54-10 = 98
132i
adalah cek utama.p
mengambil semua angka din
mana keduanyan
dan2*x+1
prima.p
adalah daftar tanpa batas.Sunting: cara yang lebih baik untuk memeriksa apakah
2*n+1
prime.sumber
Julia, 2 * 49 - 10 = 88
Mencetaknya dalam format daftar
[2,3,5,11,...]
,. Jika format itu, menggunakanprimes
fungsi, atau menunggu sampai semua perhitungan dilakukan untuk mencetak tidak dapat diterima, ini mencetak satu per baris saat dijalankan.Ini sedikit lebih lama, 52 karakter. Keduanya menghitung semua bilangan prima Sophie Germain hingga
2^33
, sehingga mereka harus mendapatkan diskon 10 poin.sumber
Python 3,
124123 byteBagaimana cara kerjanya?
Cobalah online di sini .
Komputer saya mengatakan ini telah menghasilkan 0,023283% dari semua bilangan prima Sophie Germain di bawah 2 ^ 32.
Setelah selesai, saya akan mempostingnya di pastebin jika ada cukup baris. Anda dapat menggunakannya untuk memeriksa apakah Anda memiliki semuanya.
sumber
.5
lebih pendek dari0.5
Perl, 2 * 57-10 = 104
42 detik hingga 2 ^ 32, 1m26s hingga 2 ^ 33. Akan berjalan 50% lebih cepat jika
2*$_+1
ditulis sebagai1+$_<<1
tetapi itu satu byte lagi.Modul ini juga menginstal
primes.pl
yang memiliki banyak filter termasuk satu untuk bilangan prima Sophie-Germain. Jadi:primes.pl --so 2**33
(20 byte)sumber
Ruby, 61 * 2 - 10 = 112
Butuh selamanya untuk mencetak semua nilai hingga 2 ** 32
Edit
Dicukur beberapa byte menggantikan Float :: INFINITY untuk 1.0 / 0
sumber
PARI / GP, 46 * 2 - 10 = 82
sumber