주어진 정수 N 아래의 모든 소수를 생성하는 가장 빠른 알고리즘은 무엇입니까?

N 이하의 모든 소수를 나열하는 가장 빠른 방법: 탐색

문제:

모두 나열하는 가장 빠른 방법 결정 주어진 정수보다 작은 소수 N.

질문:

주어진 알고리즘을 더 빠른 실행을 위해 최적화할 수 있습니까?

답변:

제공되는 알고리즘은 속도 측면에서 크게 향상될 수 있습니다. 다양한 구현을 비교하면 Psyco를 사용하는 rwh_primes1이 1,000,000 미만의 소수를 생성하는 데 가장 효율적이라는 것을 알 수 있습니다.

추가 조사 결과:

• Psyco가 없으면 rwh_primes2가 나타납니다. 가장 빠른 것으로
• NumPy를 활용하면 성능이 더욱 향상되며, primesfrom2는 테스트된 모든 방법 중에서 가장 빠른 것으로 입증되었습니다.

구현 세부 정보:

• ambi_sieve_plain: 간단한 체 기반 접근 방식.
• rwh_primes, rwh_primes1 및 rwh_primes2: Robert William Hanks 알고리즘의 변형.
• sieve_wheel_30: 30 기반 계산에 최적화된 특수 알고리즘.
• sieveOfEratosthenes: The 비트셋을 사용한 고전적인 체 방법 최적화.
• sieveOfAtkin: 모듈로 산술을 활용하는 현대적인 체.
• sundaram3: 더 작은 숫자 집합에 대해 최적화된 Sundaram의 알고리즘.
• ambi_sieve: NumPy를 사용한 체 기반 접근 방식 최적화.
• primesfrom3to 및 primesfrom2to: 효율적으로 소수를 생성하기 위한 NumPy 기반 알고리즘.

타이밍:

Psyco가 있는 시간(ms)147.0테이블>

방법

Psyco가 없는 시간(ms) 사이코

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

에라토스테네스 체

178.0

ambi_sieve_plain

152.0

286.0

순다람3

194.0

416.0

primesfrom2to

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

15.9

해당 없음

primesfrom3to

18.4

해당 없음

ambi_sieve

29.3

해당 없음

위 내용은 주어진 정수 N 아래의 모든 소수를 생성하는 가장 빠른 알고리즘은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!