한국어
한국어
소수는 1만큼만 나눌 수있는 자연 숫자를 나타냅니다. 소수를 찾는 것은 프로그래밍의 일반적인 문제 중 하나입니다. 이 기사는 고전적이고 효율적인 소수 솔루션 방법 인 Eratosthenes의 체를 소개합니다. 이 알고리즘은 소수와 그 배수를 표시하여 지정된 범위에서 모든 소수를 빠르게 찾습니다.
Elatoseni 필터링 방법은 장기적이고 간단하고 효과적인 알고리즘이며 핵심 아이디어는 다음과 같습니다.
True의 초기 값과 함께 길이 n+1의 부울 배열을 만듭니다.
2부터 시작하여 각 소수의 배수는 false로;
True의 최종 값이있는 요소는 소수입니다.
다음 샘플 코드는 PHP를 사용 하여이 필터링 방법을 구현하는 방법을 보여줍니다.
function sieveOfEratosthenes($n) {
// 길이를 만듭니다 n+1 부울 배열，초기 값은입니다 true
$isPrime = array_fill(2, $n - 1, true);
// ~에서2시작，각 소수의 배수 false
for ($i = 2; $i * $i <= $n; $i++) {
if ($isPrime[$i]) {
for ($j = $i * $i; $j <= $n; $j += $i) {
$isPrime[$j] = false;
}
}
}
// 모든 것을 수집하십시오 true 수의 수，즉, 소수입니다
$primes = [];
foreach ($isPrime as $number => $is) {
if ($is) {
$primes[] = $number;
}
}
return $primes;
}
$range = 100;
$primes = sieveOfEratosthenes($range);
// 출력 소수
foreach ($primes as $prime) {
echo $prime . " ";
}
이 코드는 먼저 크기 N+1의 부울 배열을 생성하고 처음에는 true로 설정 한 다음 소수의 배수를 하나씩 더블 레이어 루프를 하나씩 하나씩 표시합니다. 마지막으로, true로 표시된 모든 인덱스가 수집됩니다. 즉, 소수 세트가 수집됩니다.
위의 코드를 실행하고 100 범위의 소수의 출력은 다음과 같습니다.
<span class="fun">2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 73 79 83 89 97</span>
이 방법은 주어진 범위에서 모든 소수를 정확하고 효율적으로 찾을 수 있음을 알 수 있습니다.
Elatoseni 필터링 방법의 시간 복잡성은 O (n log log n)에 관한 것이며, 이는 중소형에서 소수의 빠른 스크리닝에 적합합니다. 폭력적인 판단과 비교할 때 선별이 크게 개선 될 때마다 더 많은 우선 순위가 배제됩니다.
이 기사는 PHP가 구현 한 Elatoseni 필터링 방법을 소개합니다. 이는 간단하고 효율적인 소수 스크리닝 알고리즘입니다. 이 알고리즘을 마스터하면 소수와 관련된 프로그래밍 문제를 해결하고 코드 효율성 및 성능을 향상시키는 데 도움이 될 수 있습니다.
