Apa yang dimaksud dengan prime home?
Sebagai contoh, ambil HP (4). Pertama, temukan faktor prima. Faktor prima dari 4 ( dalam urutan numerik dari yang paling rendah hingga yang terbesar, selalu ) adalah 2, 2. Ambil faktor-faktor tersebut sebagai angka literal. 2, 2 menjadi 22. Proses anjak piutang ini berlanjut hingga Anda mencapai bilangan prima.
number prime factors
4 2, 2
22 2, 11
211 211 is prime
Setelah Anda mencapai nomor utama, urutan berakhir. HP (4) = 211. Ini contoh yang lebih panjang, dengan 14:
number prime factors
14 2, 7
27 3, 3, 3
333 3, 3, 37
3337 47, 71
4771 13, 367
13367 13367 is prime
Tantangan Anda adalah membuat program yang akan menghitung HP (x) yang diberikan x, dan melakukannya secepat mungkin . Anda dapat menggunakan sumber daya apa pun yang Anda inginkan, selain daftar bilangan prima rumah yang dikenal.
Perhatikan, angka-angka ini menjadi sangat besar sangat cepat. Pada x = 8, HP (x) melompat jauh ke 3331113965338635107. HP (49) belum ditemukan.
Kecepatan program akan diuji pada Raspberry Pi 2, rata-rata input berikut:
16
20
64
65
80
Jika Anda memiliki Raspberry Pi 2, tentukan sendiri programnya, maka ratakan waktunya.
sumber
Jawaban:
Mathematica, HP (80) di ~ 0,88s
Fungsi anonim. Mengambil nomor sebagai input dan mengembalikan nomor sebagai output.
sumber
1
di akhir seharusnya tidak ada di sana ...CompositeQ
untuk!PrimeQ
(yang juga memastikan bahwa jawaban Anda tidak berulang input1
).HP(80)
dalam waktu yang begitu singkat tanpa harus memasang hard disk di suatu tempat? Laptop i7 saya membutuhkan waktu berjam-jam untuk melakukan pemeriksaan awal, serta menemukan faktor-faktor utama,HP(80)
ketika tiba47109211289720051
.PyPy 5.4.1 64bit (linux), HP (80) ~ 1.54s
Versi 32bit akan memakan waktu sedikit lebih lambat.
Saya menggunakan empat metode faktorisasi berbeda, dengan breakpoint yang ditentukan secara empiris:
Saya mencoba sebentar untuk menemukan jeda bersih antara ECF dan MPQS, tetapi sepertinya tidak ada. Namun, jika n mengandung faktor kecil, ECF biasanya akan segera menemukannya, jadi saya memilih untuk menguji hanya beberapa kurva, sebelum beralih ke MPQS.
Saat ini, hanya ~ 2x lebih lambat dari Mathmatica, yang saya anggap sukses.
home-prime.py
Contoh waktu
Rata-rata dari 5 adalah sekitar 0,39.
Ketergantungan
mpqs.py
diambil langsung dari jawaban saya untuk faktorisasi semiprime Tercepat dengan beberapa modifikasi yang sangat kecil.mpqs.py
my_math.py
diambil dari pos yang sama sepertimpqs.py
, namun saya juga telah menambahkan dalam bilangan prima generator tak terbatas yang saya gunakan dalam jawaban saya untuk Menemukan kesenjangan terbesar antara bilangan prima yang baik .my_math.py
sumber
Python 2 + primefac 1.1
Saya tidak punya Raspberry Pi untuk mengujinya.
Cobalah online
The
primefac
mengembalikan fungsi daftar semua faktor prima darin
. Dalam definisinya, ia memanggilisprime(n)
, yang menggunakan kombinasi divisi uji coba, metode Euler, dan uji keutamaan Miller-Rabin. Saya merekomendasikan mengunduh paket dan melihat sumbernya.Saya mencoba menggunakan
n = n * 10 ** int(floor(log10(f))+1) + f
bukan penggabungan string, tetapi jauh lebih lambat.sumber
pip install primefac
bekerja untuk saya, meskipun 65 dan 80 sepertinya tidak berjalan di windows, karenafork
ing di latar belakang.primefac
sangat lucu, karena ada banyak komentar denganTODO
ataufind out why this is throwing errors
# This occasionally throws IndexErrors.
Ya, karena dia menghapus cek bahwa ada lebih banyak smooths daripada faktor primes yang digunakan.C #
Ini adalah versi yang lebih optimal dari kode sebelumnya, dengan beberapa bagian yang tidak perlu dihapus.
Output (pada laptop i7 saya):
Tes online
sumber
Perl + teori, HP (80) dalam 0,35 detik pada PC
Tidak ada Raspberry Pi di tangan.
Tes primality adalah ES BPSW, ditambah MR berbasis acak tunggal untuk jumlah yang lebih besar. Pada ukuran ini kita bisa menggunakan
is_provable_prime
(n-1 dan / atau ECPP) tanpa perbedaan kecepatan, tetapi itu akan berubah untuk nilai> 300 digit tanpa manfaat nyata. Anjak piutang meliputi uji coba, kekuasaan, Rho-Brent, P-1, SQUFOF, ECM, QS tergantung pada ukurannya.Untuk input ini beroperasi dengan kecepatan yang sama dengan kode Charles 'Pari / GP di situs OEIS. ntheory memiliki faktorisasi yang lebih cepat untuk angka kecil, dan P-1 dan ECM saya cukup bagus, tetapi QS tidak bagus sehingga saya berharap Pari lebih cepat di beberapa titik.
sumber
use feature "say";
,.