SF (n) adalah fungsi yang menghitung faktor prima terkecil untuk angka yang diberikan n.
Kami akan memanggil T (N) jumlah setiap SF (n) dengan 2 <= n <= N.
T (1) = 0 (jumlahnya lebih dari 0 puncak)
T (2) = 2 (2 adalah prime pertama)
T (3) = 5 = 2 + 3
T (4) = 7 = 2 + 3 + 2
T (5) = 12 = 2 + 3 + 2 + 5
...
T (10000) = 5786451
Pemenang akan menjadi orang yang berhasil menghitung T (N) terbesar dalam 60 detik pada laptop saya sendiri (Toshiba Satellite L845, Intel Core i5, 8GB RAM).
Current top score: Nicolás Siplis - 3.6e13 points - Nim
math
fastest-code
primes
division
Nicolás Siplis
sumber
sumber
Jawaban:
Nim, 3.6e13
Cukup pengayakan bukanlah jawaban terbaik ketika mencoba menghitung N tertinggi karena persyaratan memori menjadi terlalu tinggi. Inilah pendekatan yang berbeda (dimulai dengan Nim beberapa hari yang lalu dan jatuh cinta dengan kecepatan dan sintaksisnya, saran untuk membuatnya lebih cepat atau lebih mudah dibaca dipersilahkan!).
sumber
return
dif
definisi 's. Prok ekspresi tunggal secara otomatis kembali.C, Prime Sieve: 5e9
Hasil:
Program:
Meskipun ini adalah program yang agak sulit, saya butuh waktu untuk mencari tahu bagaimana mendapatkan manajemen memori yang benar - saya hanya memiliki ram yang cukup untuk 1 byte per angka dalam jangkauan, jadi saya harus berhati-hati. Ini adalah saringan standar Erasthones.
sumber
Perl, anjak piutang
Saya dapat mencapai 9e7 dalam 25 detik pada mesin Linux saya. Itu bisa lebih cepat dengan menggali ke dalam kode C, seperti yang dikatakan setelah cek untuk 2/3/5, benar-benar faktor angka.
Ada banyak cara yang lebih pintar untuk melakukan ini dengan menggunakan pengayakan. Saya pikir cara kasar yang sederhana akan menjadi awal. Omong-omong, ini pada dasarnya adalah masalah Project Euler 521.
sumber
Pergi, 21e9
Apakah saringan untuk menemukan faktor minimum dari setiap angka <= N. Memunculkan goroutine untuk menghitung bagian dari ruang angka.
Jalankan dengan "go run prime.go -P 4 -N 21000000000".
Perhatikan bahwa jawaban untuk N = 21e9 adalah antara 2 ^ 63 dan 2 ^ 64, jadi saya harus menggunakan int 64-bit yang tidak ditandatangani untuk menghitung dengan benar ...
sumber
C ++, 1 << 34 ~ 1.7e10
sumber
Java 8:
1.8e82.4e8Entri ini tidak dibandingkan dengan beberapa entri lain yang sudah ada, tetapi saya ingin memposting jawaban saya karena saya senang mengerjakannya.
Optimalisasi utama dari pendekatan saya adalah sebagai berikut:
T(N)
kapanN % 2 == 1
, Anda tahu ituT(N + 1) == T(N) + 2
. Ini memungkinkan saya untuk mulai menghitung pada tiga dan meningkat dengan iterasi oleh dua atau dua.Collection
tipe. Ini lebih dari dua kali lipat yangN
bisa saya jangkau.Itu semua yang ada untuk itu. Kode saya beralih dari 3 ke dua oleh dua hingga mendeteksi bahwa ia telah mencapai atau melebihi batas waktu, pada saat itu ia mengeluarkan jawabannya.
Berjalan pada sistem yang berbeda (Windows 8.1, Intel core i7 @ 2.5 GHz, 8 GB RAM) dengan Java 8 versi terbaru memiliki hasil yang jauh lebih baik tanpa perubahan kode:
sumber
mayContinue()
infor loop condition
dengan hanya kondisi sederhana, Anda bisa mencapai hasil yang lebih tinggi. Dan saya suka cara Anda menghitung ulang bahkan jumlah, kemudian bertambah dua.startTime
ke nilaiendTime
untuk menghilangkan ~ 2e7 pengurangan, tapi itu membuat saya 3e7 dari skor saya!System.nanoTime() - startTime < TIME_LIMIT
, karena itu kencangkan kode Anda sedikit untuk saya. Ini tidak cepat, mengingat fakta, kondisi ini diperiksa jutaan kali, ini akan sedikit cepat. Satu hal yang saya pelajari dari kode Anda adalah, jangan masukkan kefor
dalamfor
.. Setelah pindahfor
ke metode lain dalam kode saya, kecepatan kode saya meningkat sebesar 40%, Terima kasih .. Satu hal yang saya masih pahami adalah, Apakah array jauh lebih efisien daripada ArrayList ketika mempertimbangkan fakta bahwa itu diambil jutaan kali ..x2
hasil jika Anda menerapkanMultiThreading
. Tetapi perlu menghitung ulang seluruh array sebelum menjalankan perhitungan Prime.mayContinue()
metode ke loop for biaya saya 8e6 dari skor saya. Ini mungkin masalah optimisasi lokal. Saya bereksperimen dengan beberapa tipe data untuk menyimpan bilangan prima ketika saya mengembangkan solusi ini. Saya hanya dapat mencapai 8.8e7 denganArrayList
, tapi saya menekan 1.8e8 (sekarang 2.4e8) menggunakan array. Mungkin ada beberapa peningkatan kinerja yang terlibat dengan pencarian, tetapi ada dorongan pasti untuk alokasi memori. Saya telah memikirkan tentang multi-threading algoritme, tetapi saya mengalami masalah.R, 2.5e7
Saringan Eratosthenes yang berpikiran sederhana, vektor sebanyak mungkin. R tidak benar-benar dirancang untuk masalah seperti ini dan saya cukup yakin itu bisa dibuat lebih cepat.
sumber
sum(vec)
mengarah ke bilangan bulat bilangan bulat dan mengembalikan NA.sum(as.numeric(vec))
menjumlahkan vektor ganda yang tidak meluap (meskipun mungkin tidak memberikan jawaban yang tepat)Python, ~ 7e8
Menggunakan Saringan tambahan Erathostenes. Beberapa kehati-hatian perlu diperhatikan bahwa nilai yang ditandai ditandai dengan pembagi terendah, tetapi implementasinya sebaliknya cukup lurus ke depan.
Waktu diambil dengan PyPy 2.6.0, input diterima sebagai argumen baris perintah.
Contoh Penggunaan
sumber
Julia, 5e7
Tentunya Julia bisa berbuat lebih baik tetapi inilah yang saya miliki untuk saat ini. Ini melakukan 5e7 dalam waktu sekitar 60 detik pada JuliaBox tapi saya belum bisa menguji secara lokal. Semoga saat itu saya akan memikirkan pendekatan yang lebih pintar.
Di sini kami membuat fungsi
lpf
yang beralih melalui bilangan prima berurutan dan memeriksa input untuk dapat dibagi oleh masing-masing. Fungsi mengembalikan pembagi pertama yang ditemukan, sehingga memperoleh faktor prima terkecil.Fungsi utama menghitung
lpf
bilangan bulat dari 2 ke input secara paralel dan mengurangi hasilnya dengan menjumlahkan.sumber
Gangguan Umum, 1e7
Saya telah memilih untuk pertama-tama menghasilkan daftar bilangan prima dari 2 hingga
(sqrt input)
, kemudian menguji setiap nilai dengan bilangan prima, sedangkan sebelumnya saya akan menguji setiap bilangan hingga(sqrt input)
, yang tidak ada gunanya (misalnya, jika angka dapat dibagi 4, itu juga habis dibagi 2, jadi sudah diperhitungkan.)Terima kasih Tuhan untuk efek samping saat saya melakukannya. Hapus-jika keduanya menurunkan ukuran daftar dan menghitung berapa banyak elemen yang dihapus, jadi saya hanya perlu mengalikannya dengan nilai berapapun loop aktif dan menambahkannya ke total berjalan.
(Fakta menyenangkan:
delete
adalah padanan yang merusakremove
, tetapi karena alasan apa pun,delete
semua jenisnya lebih lambat daripadaremove
dalam kasus ini.)sumber
Karat 1.5e9
Saringan Eratosthene yang sangat naif, tetapi saya merasa Rust tidak menerima cinta apa pun di sini!
sumber
Java 2.14e9
Saringan Murni Eratosthenes dengan keunggulan BitSet
Saya telah menghitung Terkecil faktor sum Perdana upto
Integer.MAX_VALUE - 1
hanya di33.89 s
. Tapi saya tidak bisa melanjutkan lebih besar karena lebih jauh akan mengarah ke Integer Overflow pada Ukuran Bitset. Jadi saya sedang mengerjakan untuk membuat Bitset lain untuk set Ranges berikutnya. Sampai saat itu, ini adalah yang tercepat yang bisa saya hasilkan.sumber