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

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!