에라토스테네스의 체 (소수 구하기) (feat. 백준 1978, 1929)

1. 소수란?

1과 자기 자신이외 어떠한 약수도 가지지 않는 자연수

 

<명제>

2부터 N/2 까지 나누어  떨어지는 수가 없으면 N은 소수이다.   

<근거>

p : 몫  q: 나머지

N = ap + q (0 <= q < N) // [1<= p <= N/2] [2<= a <= N/2] 이기 때문이다.

 

한마디로 몫의 최대값은 N/2  제수의 최소값은 2이기 때문에

N/2 를넘어가는 수는 절대로 N을 나머지 없이 나눌 수 없다.   

 

 

    

 

 

2. 에라토스테네스의 체 접근 Idea

 자연수 N이 소수이기 위한 조건은

보다 크지 않은 어떤 소수로도 나눠지지 않아야한다.         

 

 

 

N = a * b 라하면 a와  b가 동시에  제곱근보다 클 수 없기 때문이다. 

(바꿔 말하면 둘중 하나는 반드시 제곱근보다 작은소수이다.)       

     

<Example>

8 = 1*8, 2*4, 4*2, 8*1 

대칭성을 가지기 때문에,  1과 8(자기 자신) 을 제외한 제곱근 이하의 소수만 검사하면된다.       

 

8 = 2root2 * 2root2  

-> 반드시 두수의 곱으로 표현하면 두 수중 하나는 2root2 보다 작아질 수 밖에 없음.         

3. 문제

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

4. 소스코드

#include <iostream>
using namespace std;

bool isPrimeNumber(int n)
{
    if(n == 1)
    return false;
    else{
        for(int i = 2; i <= n/2;i++)
        {
            if(n % i == 0)
            return false;
        }
        return true;
    }
}

int main(void){
    int N, count = 0;
    cin >> N;
    int arr[N];
    for(int i = 0; i< N; i++)
    {
        cin >> arr[i];
    }
    
    for(int i = 0; i < N; i++)
    {
        if(isPrimeNumber(arr[i]))
        count++;
    }
    cout << count << endl;
    
    return 0;
}​

5. 에라토스테네스의 체 IDEA

 

알고리즘

(1) 2차원 테이블을 구성한다.

(2) 첫 소수 '2'부터 자연수 N까지 모든 배수를 지운다. (자기 자신은 제외한다)

※ 구현상으로는 원소 값을 0으로 대치한다.

(3) 숫자를 1개씩 높여가며 (2)과정을 반복한다.

이미 지워진경우 (원소 값이 0인경우) 스킵한다.

 

 

 

출처: 위키백과

5_1. 에락토스테네스 체 문제

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

5_2. C++ Code

#include <iostream>
using namespace std;

void primeNumberPrint(int arr[],int start, int N)
{
    for(int i = 2; i <= N; i++) // 모든 수에 대해 테이블 형성 
    {
        arr[i] = i;
    }
    
    for(int i = 2; i <= N;i++)
    {
        if(arr[i] == 0) // 지워져있으면 다음 수로 넘어감  
        continue;
        else
        {
        for(int j = i*2 ; j <= N; j += i)
            {
            arr[j] = 0; // 지우기 
            }
        }
    }
    for(int i = start; i <= N; i++)
    {
        if(arr[i] == 0)
        continue;
        else
        cout << arr[i] << "\n";
    }
}
int main(void)
{
    int start, endNumber; // start == M , endNumber == N
    cin >> start >> endNumber;
    int arr[endNumber+1] = {0}; // 0으로 초기화 
    primeNumberPrint(arr, start, endNumber);
    
    return 0;
}

 

 

사실 두 번째 for Loop(11번 라인)에서

i<= N이 아니라 

i <= sqrt(N) 하면 더 빠르다.

 

에라토스테네스의 체 최적화

1. i 의 검사 범위를 소수가 존재하는 제곱근까지만 검사
   제곱근만 검사하는 이유는 해당 범위에서 나올 수 있는 소수 범위가 제곱근까지만 구해도, 모두 j 에서 합성수를 지우기 때문에 양쪽에 대칭을 이루는 합성수는 j 에서 처리되기 때문이다. => 합성수가 아닌 순수 소수 범위는 제곱근 까지만 판별해도 충분하다.
2. j 의 범위를 i의 제곱수부터만 판별
   j 를 i 제곱수부터 구해도 되는 이유는 이미 j 에 도달하기 이전에 다른 수들이 이전 소수의 배수로 인해 소수가 아닌 수로 판별이 완료된 상태이기 때문이다.

 

Kotlin Code

// num: 구하고자 하는 소수의 범위 최대값
// isPrimeFlags: index: 해당 숫자, value: 소수면 true, 아니면 false
private fun sieve(num: Int, isPrimeFlags: BooleanArray) {
	// 0과 1은 소수가 아니다.
    isPrimeFlags[0] = false
    isPrimeFlags[1] = false
    // 미리 제곱근을 구한다.
    val sqrt = sqrt(num.toDouble()).toInt()

	// 2부터 제곱근까지만 돈다.
    for (i in 2 .. sqrt) {
    	// 이미 소수가 아닌 수로 판별된 경우 skip
        if (!isPrimeFlags[i]) continue
        // 해당 숫자의 제곱수부터 소수가 아닌 수를 지워나간다.
        // 이전 소수들에 의해 합성수가 이미 제거된 상태이기 때문이다.
        for (j in i * i .. num step i) {
            isPrimeFlags[j] = false
        }
    }
}

fun main(){
    val N = bufferedReader.readLine().toInt()

    if (N == 1) {
        print(0)
        return
    }

	// 모든 수를 소수로 초기화
    val isPrimeFlags = BooleanArray(N + 1){true}
    sieve(N, isPrimeFlags)
    // isPrimeFlags 에서 true 로 표시된 index 는 소수.
}