Tantangan
Dalam tugas ini Anda akan diberi integer N Anda harus menampilkan bilangan prima terdekat ke bilangan bulat.
Jika bilangan prima itu sendiri menghasilkan bilangan.
Input N diberikan dalam satu baris, input diakhiri oleh EOF. Jumlah input tidak akan melebihi nilai 10000.
Tantangannya adalah untuk mengimplementasikan solusi tercepat sehingga dapat memproses maksimal 10.000 nilai secepat mungkin.
Memasukkan
299246598
211571591
71266182
645367642
924278231
Keluaran
299246587
211571573
71266183
645367673
924278233
Kendala
- N kurang dari 2 ^ 64
- Jaga jari-jari Anda jangan gunakan lebih dari 4096 byte dalam solusi Anda.
- Anda dapat menggunakan bahasa apa pun pilihan Anda selama Anda tidak menggunakan bahasa inbuilt untuk bilangan prima.
- Solusi tercepat, dengan kompleksitas waktu paling efisien menang!
TAMBAH:
Ini adalah versi yang lebih mudah dari masalah yang sama ini (dengan N <2 ^ 31) sehingga Anda dapat mencoba memeriksa pendekatan Anda dalam kasus yang lebih kecil sebelum membangunnya untuk masalah yang sebenarnya ini.
code-challenge
primes
fastest-algorithm
Pemurah
sumber
sumber
Jawaban:
Python
sumber
PARI GP
sumber
NextPrime[n]
berfungsi secara ketat di atasn
sehingga 3 syarat ....Haskell
Seharusnya cukup cepat. Membutuhkan paket
primes
, tersedia dari peretasan.sumber
Rubi
sumber
Jawa
Ini membutuhkan waktu <1 detik hingga num mulai lebih besar dari 10 ^ 8. Tidak cukup efisien, mengingat 2 ^ 64 adalah sekitar 1,8 * 10 ^ 19. (Dimulai 10 ^ 15 6 menit yang lalu, dan masih berjalan D :)
Ini memberikan jawaban yang pasti setiap kali, karena tidak menggunakan algoritma probabilistik, tetapi membayar mahal untuk itu dalam hal efisiensi - 10 ^ 18 akan memiliki lebih dari 5 juta bilangan prima dalam daftar, dan bahkan lebih sebelum menyaring. Dapat meningkatkan ini kadang dengan algoritma ayakan yang lebih baik. Saya tidak berharap ini mengalahkan yang lain :)
sumber
Haskell
Ini cukup cepat, dan non-deterministik hingga batas yang besar. Juga Haskell pertama saya :).
wc
kata 903b tidak dikompilasi.Sunting: Jika ada yang ingin memperkirakan kerumitan waktu, jadilah tamu saya ...
sumber