Apakah Algoritma Terpantas untuk Menjana Semua Nombor Perdana Di Bawah Integer N Diberi?-Tutorial Python-php.cn

Rumah

pembangunan bahagian belakang

Tutorial Python

Apakah Algoritma Terpantas untuk Menjana Semua Nombor Perdana Di Bawah Integer N Diberi?

DDD

Dec 18, 2024 am 02:35 AM

What's the Fastest Algorithm to Generate All Prime Numbers Below a Given Integer N?

Cara Terpantas untuk Menyenaraikan Semua Perdana Di Bawah N: Satu Penerokaan

Masalah:

Tentukan kaedah terpantas untuk menyenaraikan semua nombor perdana kurang daripada integer tertentu N.

Soalan:

Bolehkah algoritma yang diberikan dioptimumkan untuk pelaksanaan yang lebih pantas?

Jawapan:

Algoritma yang disediakan boleh dipertingkatkan dengan ketara untuk kelajuan. Perbandingan pelbagai pelaksanaan mendedahkan bahawa rwh_primes1 dengan Psyco adalah yang paling cekap untuk menjana bilangan prima kurang daripada 1,000,000.

Penemuan Tambahan:

Tanpa Psyco, rwh_primes2 sebagai yang terpantas kaedah.
Menggunakan NumPy menawarkan peningkatan prestasi selanjutnya, dengan primesfrom2hingga terbukti sebagai yang terpantas antara semua kaedah yang diuji.

Butiran Pelaksanaan:

ambi_sieve_plain: Berasaskan ayak yang mudah pendekatan.
rwh_primes, rwh_primes1 dan rwh_primes2: Variasi algoritma Robert William Hanks.
sieve_wheel_30: Algoritma khusus yang dioptimumkan untuk pengiraan berasaskan 30.

sieve_wheel_30: kaedah ayak klasik dengan bitset pengoptimuman.

sieveOfAtkin: Ayak moden menggunakan aritmetik modulo.

sundaram3: Algoritma Sundaram dengan pengoptimuman untuk set nombor yang lebih kecil.

ambi_sieve: Pendekatan berasaskan ayak dengan NumPy pengoptimuman.

primesfrom3to dan primesfrom2to: Algoritma berasaskan NumPy untuk menjana nombor prima dengan cekap.

Masa: Kaedah Masa (ms) dengan Psiko Masa (ms) tanpa Psiko rwh_primes1 43.0 93.7 sieveOfAtkin 46.4 314.0 rwh_primes 57 .4 94.6 ayak_roda_30 63.0 97.4 rwh_primes2 67.8 68.1 sieveOfEratosthenes147.0178.0 ambi_sieve_plain 152.0 286.0 sundaram3 194.0 416.0 primesfrom2to 15.9

Method	Time (ms) with Psyco	Time (ms) without Psyco
rwh_primes1	43.0	93.7
sieveOfAtkin	46.4	314.0
rwh_primes	57.4	94.6
sieve_wheel_30	63.0	97.4
rwh_primes2	67.8	68.1
sieveOfEratosthenes	147.0	178.0
ambi_sieve_plain	152.0	286.0
sundaram3	194.0	416.0
primesfrom2to	15.9	N/A
primesfrom3to	18.4	N/A
ambi_sieve	29.3	N/A

T/A primesfrom3to 18.4 N/A ambi_sieve 29.3 T/A jadual>

Atas ialah kandungan terperinci Apakah Algoritma Terpantas untuk Menjana Semua Nombor Perdana Di Bawah Integer N Diberi?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan

Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Artikel Berkaitan

Cara Menggunakan Python untuk Mencari Pengagihan Zipf Fail TeksMar 05, 2025 am 09:58 AM

Tutorial ini menunjukkan cara menggunakan Python untuk memproses konsep statistik undang -undang ZIPF dan menunjukkan kecekapan membaca dan menyusun fail teks besar Python semasa memproses undang -undang. Anda mungkin tertanya -tanya apa maksud pengedaran ZIPF istilah. Untuk memahami istilah ini, kita perlu menentukan undang -undang Zipf. Jangan risau, saya akan cuba memudahkan arahan. Undang -undang Zipf Undang -undang Zipf hanya bermaksud: Dalam korpus bahasa semulajadi yang besar, kata -kata yang paling kerap berlaku muncul kira -kira dua kali lebih kerap sebagai kata -kata kerap kedua, tiga kali sebagai kata -kata kerap ketiga, empat kali sebagai kata -kata kerap keempat, dan sebagainya. Mari kita lihat contoh. Jika anda melihat corpus coklat dalam bahasa Inggeris Amerika, anda akan melihat bahawa perkataan yang paling kerap adalah "th

Bagaimana saya menggunakan sup yang indah untuk menghuraikan html?Mar 10, 2025 pm 06:54 PM

Artikel ini menerangkan cara menggunakan sup yang indah, perpustakaan python, untuk menghuraikan html. Ia memperincikan kaedah biasa seperti mencari (), find_all (), pilih (), dan get_text () untuk pengekstrakan data, pengendalian struktur dan kesilapan HTML yang pelbagai, dan alternatif (sel

Penapisan gambar di pythonMar 03, 2025 am 09:44 AM

Berurusan dengan imej yang bising adalah masalah biasa, terutamanya dengan telefon bimbit atau foto kamera resolusi rendah. Tutorial ini meneroka teknik penapisan imej di Python menggunakan OpenCV untuk menangani isu ini. Penapisan Imej: Alat yang berkuasa Penapis Imej

Bagaimana untuk melakukan pembelajaran mendalam dengan Tensorflow atau Pytorch?Mar 10, 2025 pm 06:52 PM

Artikel ini membandingkan tensorflow dan pytorch untuk pembelajaran mendalam. Ia memperincikan langkah -langkah yang terlibat: penyediaan data, bangunan model, latihan, penilaian, dan penempatan. Perbezaan utama antara rangka kerja, terutamanya mengenai grap pengiraan

Pengenalan kepada pengaturcaraan selari dan serentak di PythonMar 03, 2025 am 10:32 AM

Python, kegemaran sains dan pemprosesan data, menawarkan ekosistem yang kaya untuk pengkomputeran berprestasi tinggi. Walau bagaimanapun, pengaturcaraan selari dalam Python memberikan cabaran yang unik. Tutorial ini meneroka cabaran -cabaran ini, memberi tumpuan kepada Interprete Global

Cara Melaksanakan Struktur Data Anda Sendiri di PythonMar 03, 2025 am 09:28 AM

Tutorial ini menunjukkan mewujudkan struktur data saluran paip tersuai di Python 3, memanfaatkan kelas dan pengendali yang berlebihan untuk fungsi yang dipertingkatkan. Fleksibiliti saluran paip terletak pada keupayaannya untuk menggunakan siri fungsi ke set data, GE

Serialization dan deserialisasi objek python: Bahagian 1Mar 08, 2025 am 09:39 AM

Serialization dan deserialization objek Python adalah aspek utama dari mana-mana program bukan remeh. Jika anda menyimpan sesuatu ke fail python, anda melakukan siri objek dan deserialization jika anda membaca fail konfigurasi, atau jika anda menjawab permintaan HTTP. Dalam erti kata, siri dan deserialization adalah perkara yang paling membosankan di dunia. Siapa yang peduli dengan semua format dan protokol ini? Anda mahu berterusan atau mengalirkan beberapa objek python dan mengambilnya sepenuhnya pada masa yang akan datang. Ini adalah cara yang baik untuk melihat dunia pada tahap konseptual. Walau bagaimanapun, pada tahap praktikal, skim siri, format atau protokol yang anda pilih boleh menentukan kelajuan, keselamatan, kebebasan status penyelenggaraan, dan aspek lain dari program

Modul Matematik dalam Python: StatistikMar 09, 2025 am 11:40 AM

Modul Statistik Python menyediakan keupayaan analisis statistik data yang kuat untuk membantu kami dengan cepat memahami ciri -ciri keseluruhan data, seperti biostatistik dan analisis perniagaan. Daripada melihat titik data satu demi satu, cuma melihat statistik seperti min atau varians untuk menemui trend dan ciri dalam data asal yang mungkin diabaikan, dan membandingkan dataset besar dengan lebih mudah dan berkesan. Tutorial ini akan menjelaskan cara mengira min dan mengukur tahap penyebaran dataset. Kecuali dinyatakan sebaliknya, semua fungsi dalam modul ini menyokong pengiraan fungsi min () dan bukan hanya menjumlahkan purata. Nombor titik terapung juga boleh digunakan. Import secara rawak Statistik import dari fracti

See all articles