에라토스테네스의 체를 사용하여 Java에서 어떻게 우아하게 소수를 생성할 수 있습니까?

Java의 에라토스테네스의 체: 우아하게 소수 생성

소개

소수 생성은 다양한 알고리즘 중에서 선택할 수 있는 컴퓨터 과학의 근본적인 문제입니다. 그 중 에라토스테네스의 체는 단순성과 효율성으로 유명합니다. 이 기사에서는 에라토스테네스의 체를 사용하여 처음 n개의 소수를 생성하는 우아한 Java 구현을 제공합니다.

에라토스테네스의 체

에라토스테네스의 체는 소수의 배수를 반복적으로 제거하여 소수를 식별하는 확률적 알고리즘입니다. 먼저 부울 플래그 배열을 초기화합니다. 각 플래그는 지정된 제한까지의 숫자를 나타냅니다. 그런 다음 알고리즘은 첫 번째 소수 2부터 시작하여 배열을 반복하고 모든 배수를 소수가 아닌 것으로 표시합니다. 이 과정은 한계 내의 모든 숫자가 제거되고 소수만 남을 때까지 계속됩니다.

우아한 구현

에라토스테네스의 체의 우아한 Java 구현은 다음과 같습니다.

<code class="language-java">public static BitSet computePrimes(int limit) {
    final BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 2; i * i <= limit; i++) {
        if (primes.get(i)) {
            for (int j = i * i; j <= limit; j += i) {
                primes.set(j, false);
            }
        }
    }
    return primes;
}</code>

설명

이 구현은 각 비트가 지정된 제한까지의 숫자를 나타내는 BitSet을 생성합니다. 처음에는 0과 1이 소수가 아닌 것으로 표시되고 다른 모든 숫자는 소수로 표시됩니다.

외부 루프는 첫 번째 소수 2부터 시작하여 배열을 반복합니다. 현재 위치의 비트가 설정되면(소수임을 나타냄) 내부 루프는 해당 소수의 모든 배수를 소수가 아닌 것으로 표시합니다. 이 프로세스는 한도 내의 모든 숫자가 제거될 때까지 계속됩니다.

마지막으로 소수가 포함된 BitSet을 반환합니다.

결론

에라토스테네스의 체에 대한 이 Java 구현은 알고리즘의 우아함과 단순성을 보여줍니다. 소수를 효율적으로 생성하고 명확하고 논리적인 구조를 가지고 있습니다. 이 코드는 성능과 이해 가능성에 최적화되어 소수 생성기가 필요한 프로그래머에게 유용한 도구입니다.

위 내용은 에라토스테네스의 체를 사용하여 Java에서 어떻게 우아하게 소수를 생성할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!