에라토스테네스의 체 알고리즘: Python, C++ 예시
사라 첸
에라토스테네스의 체는 가장 간단한 소수 체입니다. 주어진 한계 내에서 모든 소수를 검색하는 소수 알고리즘입니다. 소수 체에는 여러 가지가 있습니다. 예를 들어 에라토스테네스의 체, 아트킨의 체, 순다람의 체 등이 있습니다.
단어 "체”은 물질을 걸러내는 기구를 뜻한다. 따라서 시브 알고리즘은 Python 그리고 다른 언어에서는 소수를 걸러내는 알고리즘을 말합니다.
이 알고리즘은 반복적 접근 방식으로 소수를 걸러냅니다. 필터링 프로세스는 가장 작은 소수부터 시작합니다. 소수는 1보다 크고 약수가 1과 그 자체인 자연수입니다. 소수가 아닌 숫자를 합성수라고 합니다.
에라토스테네스 방법의 체에서는 작은 소수가 먼저 선택되고 그 소수의 모든 배수가 필터링됩니다. 프로세스는 주어진 범위의 루프에서 실행됩니다.
예 :
2에서 10까지의 숫자 범위를 살펴보겠습니다.
에라토스테네스의 체를 적용하면 2, 3, 5, 7의 소수 목록이 생성됩니다.
에라토스테네스의 알고리즘 체
에라토스테네스의 체 알고리즘은 다음과 같습니다.
단계 1) 2부터 주어진 범위 n까지의 숫자 목록을 만듭니다. 우리는 가장 작고 첫 번째 소수인 2부터 시작합니다.
단계 2) 목록에서 가장 작은 숫자 x를 선택합니다(처음에는 x가 2와 같음). 목록을 탐색하고 선택한 숫자의 모든 배수를 표시하여 해당 합성수를 필터링합니다.
단계 3) 그런 다음 목록에서 다음 소수 또는 표시되지 않은 가장 작은 숫자를 선택하고 2단계를 반복합니다.
단계 4) x 값이 n의 제곱근보다 작거나 같아질 때까지 이전 단계를 반복합니다(x<=
).
참고 : 수학적 추론은 매우 간단합니다. 숫자 범위 n은 다음과 같이 인수분해될 수 있습니다.
n=a*b
다시 말하지만, n =*
= (보다 작은 요소 ) * (보다 큰 요인 )
그래서 적어도 하나는 소인수 또는 둘 다 <=이어야 합니다.. 따라서 충분합니다.
단계 5) 이 네 단계를 거친 후, 표시되지 않은 나머지 숫자는 주어진 범위 n에 있는 모든 소수가 됩니다.
예:
예를 들어 어떻게 작동하는지 살펴보겠습니다.
이 예시에서 우리는 2에서 25까지의 소수 목록을 찾을 것입니다. 따라서 n=25입니다.
단계 1) 첫 번째 단계에서는 n=2를 선택했으므로 25부터 25까지의 숫자 목록을 가져옵니다.
단계 2) 그런 다음 목록에서 가장 작은 숫자 x를 선택합니다. 처음에는 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까지의 소수입니다.
의사 코드
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++ 코드 예
#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 프로그램 예
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에 그렇게 큰 메모리 공간을 할당하는 것은 실행 불가능합니다.
알고리즘은 몇 가지 새로운 기능을 도입하여 최적화할 수 있습니다. 아이디어는 숫자 범위를 더 작은 세그먼트로 나누고 해당 세그먼트에서 소수를 하나씩 계산하는 것입니다. 이는 공간 복잡도를 줄이는 효율적인 방법입니다. 이 방법을 분할 체.
최적화는 다음과 같은 방식으로 달성할 수 있습니다.
- 간단한 체를 사용하여 2에서 소수를 찾으세요.
그리고 배열에 저장합니다. - 범위 [0…n-1]을 최대 크기의 여러 세그먼트로 나눕니다.
- 각 세그먼트에 대해 세그먼트를 반복하고 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)))입니다.
다음으로 알아볼 내용은 파스칼의 삼각형
요약
- 에라토스테네스의 체는 주어진 상한 내의 소수를 걸러냅니다.
- 소수 필터링은 가장 작은 소수인 "2"부터 시작됩니다. 이는 반복적으로 수행됩니다.
- 반복은 n의 제곱근까지 수행됩니다. 여기서 n은 주어진 숫자 범위입니다.
- 이러한 반복 과정을 거친 후 남는 숫자가 소수입니다.
