에라토스테네스의 체 Python & C++

에라토스테네스의 체란 무엇인가?

에라토스테네스의 체는 가장 간단한 소수 판별법입니다. 이는 주어진 범위 내의 모든 소수를 찾아내는 데 사용되는 소수 판별 알고리즘입니다. 에라토스테네스의 체, 앳킨의 체, 순다람의 체 등 여러 종류의 소수 판별법이 존재합니다.

단어 "체"체"는 물질을 걸러내는 도구를 의미합니다. 같은 맥락에서, 체 알고리즘은 다음과 같습니다. Python 그리고 다른 언어에서는 정수 목록에서 소수를 걸러내는 방법을 가리킵니다.

이 알고리즘은 반복적인 접근 방식을 사용하여 소수를 필터링합니다. 필터링 과정은 가장 작은 소수부터 시작합니다. 소수란 1보다 큰 자연수 중에서 약수가 1과 자기 자신 두 개뿐인 수를 말합니다. Numbers 소수가 아닌 수들을 합성수라고 합니다.

에라토스테네스의 체를 사용하는 이유는 무엇일까요?

에라토스테네스의 체는 먼저 작은 소수 하나를 선택하고, 그 소수의 배수를 모두 걸러내는 방법입니다. 이 과정은 주어진 범위 내에서 반복적으로 수행되어, 각 후보에 대해 시행착오를 거치지 않고도 n까지의 모든 소수를 효율적으로 찾아냅니다.

이러한 방식 덕분에 소수 판별을 하나씩 하는 것보다 훨씬 빠르게 소수를 찾아낼 수 있습니다. 소수를 빠르게 생성해야 하는 정수론, 암호학, 해싱, 경쟁 프로그래밍 등 다양한 분야에서 널리 사용됩니다.

예 :

2부터 10까지의 숫자 범위를 생각해 봅시다.

에라토스테네스의 체를 적용하면 소수 2, 3, 5, 7의 목록이 나옵니다.

에라토스테네스의 알고리즘 체

에라토스테네스의 체 알고리즘은 다음과 같습니다.

단계 1) 2부터 주어진 범위 n까지의 숫자로 이루어진 리스트를 만드세요. 2는 가장 작고 첫 번째 소수이므로 2부터 시작합니다.

단계 2) 목록에서 가장 작은 숫자 x(초기값은 2)를 선택하고, 목록을 순회하면서 선택한 숫자의 배수인 합성수들을 모두 표시합니다.

단계 3) 그런 다음 목록에서 다음 소수 또는 표시되지 않은 가장 작은 숫자를 선택하고 2단계를 반복합니다.

단계 4) x의 값이 n의 제곱근 이하(x<= n)가 될 때까지 이전 단계를 반복합니다.).

참고 : 수학적 추론은 매우 간단합니다. 수의 범위 n은 다음과 같이 인수분해될 수 있습니다.

n = a * b

다시 말하지만, n = *

= (보다 작은 요소 ) * (보다 큰 요인 )

그래서 적어도 하나는 소인수 또는 둘 다 <=이어야 합니다. 그러므로, 최대 충분합니다.

단계 5) 위 네 단계를 거치면, 표시되지 않은 나머지 숫자들은 주어진 범위 n에 있는 모든 소수가 됩니다.

풀이 예시

예:

예를 들어 어떻게 작동하는지 살펴보겠습니다.

이 예시에서는 2부터 25까지의 소수 목록을 찾아보겠습니다. 따라서 n = 25입니다.

단계 1) 첫 번째 단계에서는 n=25를 선택했으므로 2부터 25까지의 숫자 목록을 가져옵니다.

단계 2) 다음으로 목록에서 가장 작은 숫자 x를 선택합니다. 처음에는 가장 작은 소수인 2를 선택합니다. 그런 다음 목록을 순회하면서 2의 배수를 표시합니다.

주어진 n 값에 대한 2의 배수는 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24입니다.

참고 : 파란색은 선택된 숫자를 나타내고, 분홍색은 제거된 배수를 나타냅니다.

단계 3) 그런 다음 표시되지 않은 다음으로 가장 작은 숫자인 3을 선택하고 3의 배수를 표시하여 마지막 단계를 반복합니다.

단계 4) x = 이 될 때까지 3단계를 같은 방식으로 반복합니다. 또는 5.

단계 5) 표시되지 않은 나머지 숫자는 2부터 25까지의 소수입니다.

가짜-Code

다음 의사 코드는 에라토스테네스의 체를 실제 코드로 변환하기 전에 기본적인 구조를 나타냅니다.

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

에라토스테네스의 체 C/C++ Code 예시

아래는 전체 내용입니다. C++ 선택한 상한값까지의 모든 소수를 출력하는 에라토스테네스의 체 구현체입니다.

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    }
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
}

출력:

2 3 5 7 11 13 17 19 23

에라토스테네스의 체 Python 프로그램 예

다음 Python 이 프로그램은 불리언 리스트와 while 루프를 사용하여 동일한 알고리즘을 구현합니다.

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

출력:

2
3
5
7
11
13
17
19
23

분할된 체

우리는 에라토스테네스의 체가 전체 수의 범위를 순환한다는 것을 알았습니다. 따라서 숫자를 저장하는 데 O(n)의 메모리 공간이 필요합니다. 하지만 매우 큰 범위에서 소수를 찾으려고 할 때는 상황이 복잡해집니다. 왜냐하면 큰 n에 대해 그렇게 큰 메모리 블록을 할당하는 것은 현실적으로 불가능하기 때문입니다.

알고리즘은 몇 가지 새로운 기능을 도입하여 최적화할 수 있습니다. 아이디어는 숫자 범위를 더 작은 세그먼트로 나누고 해당 세그먼트에서 소수를 하나씩 계산하는 것입니다. 이는 공간 복잡도를 줄이는 효율적인 방법입니다. 이 방법을 분할 체.

최적화는 다음과 같은 방식으로 달성할 수 있습니다.

1. 간단한 체를 사용하여 2에서 소수를 찾으세요. 그리고 배열에 저장합니다.
2. 범위 [0…n-1]을 최대 크기의 여러 세그먼트로 나눕니다. .
3. 각 구간에 대해, 해당 구간을 순회하면서 1단계에서 찾은 소수의 배수를 표시합니다. 이 단계는 O(최대치로.

일반 체에는 O(n) 보조 메모리 공간이 필요한 반면, 분할 체에는 O(이는 n이 클 경우 상당한 개선을 의미합니다. 하지만 이 방법에는 시간 복잡도를 개선하지 못한다는 단점도 있습니다.

복잡성 분석

공간 복잡도와 시간 복잡도를 모두 이해하면 주어진 문제 크기에 대해 일반 체와 분할 체 중에서 어떤 방법을 선택할지 결정하는 데 도움이 됩니다.

공간 복잡성 :

단순 에라토스테네스의 체 알고리즘은 O(n)의 메모리 공간을 필요로 합니다. 분할된 체는 O() 보조 공간.

시간 복잡성 :

일반적인 에라토스테네스의 체 알고리즘의 시간 복잡도는 O(n*log(log(n)))입니다. 이러한 복잡도의 근거는 아래에서 설명합니다.

주어진 숫자 n에 대해 합성수(즉, 소수가 아닌 수)를 표시하는 데 필요한 시간은 일정합니다. 따라서 반복문이 실행되는 횟수는 다음과 같습니다.

n/2 + n/3 + n/5 + n/7 + …

= n * (1/2 + 1/3 + 1/5 + 1/7 +…

소수의 합의 조화 진행은 log(log(n))으로 유도될 수 있습니다.

(1/2 + 1/3 + 1/5 + 1/7 +…….무한) = 로그(로그(n))

따라서 시간 복잡도는 다음과 같습니다.

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

=n * 로그(로그(n))

따라서 시간 복잡도는 O(n * log(log(n)))입니다.

다음으로, 여러분은 다음 내용을 배우게 될 것입니다. 파스칼의 삼각형.

자주 묻는 질문