주어진 정수 N 아래의 모든 소수를 찾는 가장 빠른 방법은 무엇입니까?

N 아래의 모든 소수를 나열하는 가장 빠른 방법

이 코드 조각은 소수 목록을 효율적으로 생성하는 방법의 Python 구현을 제공합니다. 주어진 정수까지.

    def get_primes(n):
        numbers = set(range(2, n + 1))
        primes = []
        while numbers:
            p = numbers.pop()
            primes.append(p)
            numbers.difference_update(set(range(p * p, n + 1, p)))
        return primes

시간 복잡도:

주어진 코드의 시간 복잡도는 O(n log log n)입니다. 이는 에라토스테네스의 체를 사용하여 소수를 계산하기 때문입니다.

구현 참고 사항 :

• 코드는 2부터 까지의 모든 정수를 포함하는 집합 숫자를 초기화합니다. n.
• 아직 표시되지 않은 가장 작은 숫자의 모든 배수를 합성으로 표시하여 숫자에서 소수가 아닌 숫자를 반복적으로 제거합니다. 숫자를 업데이트할 때 현재 소수를 사용하여 이러한 배수를 건너뜁니다.
• 숫자가 비어 있으면 코드가 중지되고 발견된 소수 목록이 소수로 반환됩니다.

잠재적인 문제:

시작 숫자를 소수로 표시하는 구현에 잠재적인 문제가 있습니다. 2에서 n까지의 숫자만 고려해야 하는 경우 숫자입니다. 0 대신 2에서 루프를 시작하면 이 문제를 해결할 수 있습니다.

사용법:

이 구현을 사용하려면 get_primes 함수를 호출하고 원하는 상위 값을 전달할 수 있습니다. 인수로 바인딩됩니다. 예를 들어, 최대 1000까지의 모든 소수를 찾으려면 다음을 사용할 수 있습니다.

primes = get_primes(1000)

출력:

코드의 출력은 소수 목록이 됩니다. 지정된 정수까지의 숫자입니다. 예를 들어 n = 1000으로 코드를 실행하면 다음과 같은 출력이 생성됩니다.

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..., 977]

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