주어진 범위 내의 모든 소수를 어떻게 효율적으로 찾을 수 있습니까?

주어진 범위 내에서 소수 찾기: 최적화된 접근 방식

이 문서에서는 지정된 범위 내의 모든 소수를 효율적으로 식별하는 과제를 다룹니다. 소수는 정의상 1과 자기 자신 외에 양의 약수가 없는 1보다 큰 자연수입니다.

잘못된 접근방식과 그 수정

이 문제를 해결하려는 초기 시도에는 논리에 심각한 결함이 있었습니다. 코드는 0에서 반복되어 0과 1을 잠재적 소수로 잘못 포함하고 잘못된 소수성 테스트를 사용했습니다. if (i != j && i % j == 0) 조건은 소수가 아닌 합성수를 식별합니다. 올바른 접근 방식은 숫자가 1과 자신 이외의 숫자로 나누어지지 않는지 확인하는 것입니다.

시험분할체를 이용한 최적화 솔루션

훨씬 더 효율적인 방법은 시험 분할 체를 활용하는 것입니다. 이 접근 방식은 몇 가지 주요 최적화를 활용합니다.

1. 제곱근 한계: 목표 숫자의 제곱근까지만 가분성을 테스트하면 됩니다. 숫자에 제곱근보다 큰 약수가 있으면 제곱근보다 작은 약수도 있어야 합니다.

2. 다중 제거: 소수가 식별되면 해당 배수가 후보 목록에서 제거되어 후속 확인 횟수가 크게 줄어듭니다.

3. 반복 추정: 코드는 근사 공식(π(x) < 1.26 x / ln(x), 여기서 π(x)는 소수 계산 함수)을 사용하여 최대 수를 추정합니다. 반복이 필요하므로 효율성이 더욱 향상됩니다.

최적화된 코드(간결성을 위해 LINQ 사용)는 다음 전략을 효과적으로 구현합니다.

Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
    Enumerable.Range(2, num-1).ToList(), 
    (result, index) => { 
        var bp = result[index]; var sqr = bp * bp;
        result.RemoveAll(i => i >= sqr && i % bp == 0); 
        return result; 
    }
);
</p>
<p>이 세련된 알고리즘은 특히 광범위한 범위를 처리할 때 순진한 접근 방식에 비해 상당한 성능 향상을 제공합니다.  <code>Enumerable.Range, ToList, RemoveAll, Aggregate을 사용하면 간결하고 효율적인 구현이 가능합니다.


위 내용은 주어진 범위 내의 모든 소수를 어떻게 효율적으로 찾을 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!