JUNGOL 실력키우기 2813 : 소수의 개수

소수(prime number)란 1보다 큰 자연수 중 1과 자기 자신 두 개만을 약수로 갖는 수를 말한다.
자연수 M과 N을 입력받아 M부터 N까지 소수의 개수를 구하여 출력하는 프로그램을 작성하시오.

자연수 M과 N이 공백으로 구분되어 주어진다. (1 ≤ M ≤ N ≤  2,000,000)

M이상 N이하의 자연수 중 소수가 몇 개인지 구하여 출력한다.

[Copy] 10 100

[Copy] 21

---

 

 

시간 제한을 두고 생각하다 보니 단순하게 반복문 돌리는건 시도조차 안하게 되는군요. 어쨋거나 이번에는 JUNGOL에서 제대로  HINT를 만들어 줘서 그걸 보고 제 나름대로 프로그램을 만들어 해결해 보았습니다.

 

 

코드1
 int prime(int x)
 {
     int i;
     for (i=2; i*i<=x; i++) {
         if (x%i == 0) return 0;  // 약수가 확인되면 소수가 아니므로 0을 리턴한다.
     }
     return 1;                   // 범위내에 약수가 없으면 소수이므로 1을 리턴한다.
 }

int main()
 {
     ...
     for (i=s; i<=e; i++) {
         cnt += prime(i);        //만약 i가 소수이면 1이 리턴되므로 cnt를 1 증가시킨다.
     }
     printf("%d\n", cnt);
    ...
 }

코드분석
 앞에서 배운 방법으로 범위내의 모든 수들이 소수인지 아닌지 확인하여 소수의 개수를 누적하여 출력하는 프로그램이다.
 이 코드의 시간복잡도는 O(N)으로 비록 많이 줄이긴 했지만 최대값이 입력되면 여전히 시간이 초과될 위험이 있다. 
 이러한 부담을 줄이기 위해 일정 범위내의 소수를 빠르게 구하는 새로운 방법을 알아보도록 하자.

알아두기
에라토스테네스의 체(Eratosthenes' sieve)
에라토스테네스가 일정 범위까지의 소수를 간단하게 구하기 위해 고안한 방법으로 자연수를 ‘체’로 쳐서 걸러내고 ‘소수’만
 골라내는 방법이라고 해서 에라토스테네스의 체라고 한다.

이런 방법으로 1부터 30까지의 소수를 구하는 과정을 살펴보자.

1. 먼저 1은 정의상 소수가 아니므로 걸러낸다. (제거한다.)


2. 남은 수들중 가장 작은 수는 2이므로 소수에 추가하고 2의 배수를 모두 걸러낸다.


3. 남은 수들중 가장 작은 수는 3이므로 소수에 추가하고 3의 배수를 모두 걸러낸다.


4. 남은 수들중 가장 작은 수는 5이므로 소수에 추가하고 5의 배수를 모두 걸러낸다.


이런 방법으로 모든 수를 소수에 추가하거나 걸러내면 끝나게 된다.

그런데 여기에서 4번에서 5를 처리하는 과정을 생각해 보자.
 5를 소수에 추가하고 30까지 5보다 큰 5의 배수를 모두 걸러내야 하는데
 5 * 2 = 10
 5 * 3 = 15
 5 * 4 = 20
 5 * 5 = 25 
 5 * 6 = 30

위와 같이 걸러낼 값이 5개가 있는데 10은 2의 배수일 때, 15는 3의 배수일 때, 20은 4의 배수일 때
(실제로는 4가 2의 배수이므로 2의 배수일 때) 이미 모두 제거가 된 것이다.

즉, 5보다 작은 수를 곱해서 생기는 5의 배수는 5를 처리하기 이전에 모두 제거가 되었다는 것이다.
따라서 5를 처리할 때에는 5의 제곱인 25부터만 처리하면 된다.

그렇다면 다음 7을 처리할 때에는 7의 제곱이 49로 30을 초과하기 때문에 더 이상 처리할 게 없으므로
 그 때까지 제거되지 않고 남아 있는 7, 11, 13, 17, 19, 23, 29는 모두 소수가 되는 것이다.

이렇게 에라토스테네스의 체를 이용하여 어떤 수(N)까지의 소수를 구하기 위해서, N의 제곱근까지만 배수를 
걸러내는 작업을 하면 되므로 매우 빠른 속도로 소수를 구해 낼 수 있다.

코드2

 int prime[2000005];

void eratos(int n)
 {
     int i, j;
     prime[1]=1;
     for (i=2; i*i <= n; i++) {
         if (prime[i]==0) {
             for (j=i*i; j<=n; j+=i) {  // i의 제곱부터 n까지 i씩 증가 
                 prime[j] = 1;       // i의 배수 제거하기
             }
         }
     }
 }

int main()
 {
     int s, e, i;
     int cnt = 0;
     scanf("%d %d", &s, &e);
     eratos(e);
     for (i=s; i <= e; i++) {
         if(prime[i]==0) cnt++;
     }
     printf("%d\n", cnt);
     return 0;
 }

eratos는 에라토스테네스의 체를 이용하여 prime배열에서 n까지 소수가 아닌 수들을 1로 바꾸어 주는 함수이다.
 함수를 실행하고 나면 소수는 모두 0이 그대로 있고 1과 합성수는 모두 1로 바뀌어 있다.

            for (j=i*i; j <= n; j+=i) {  
                 prime[j] = 1;       
             }

위의 코드는 다음과 같이 써도 같은 내용이다..

            for (j=i; i*j <= n; j++) {  
                 prime[i*j] = 1;     
             }

 

#include <iostream>
 
using namespace std;
 
// 소수와 합성수를 표현
enum { PRIME = 0, COMPOSIT = 1 };
 
int Eratos(int* arr, int M, int N);
 
int main(void)
{
    int *arr;
    int M, N;
 
    cin >> M >> N;
 
    arr = new int[N];
    for (int i = 0; i < N; ++i)
    {
        arr[i] = i + 1;
    }
 
    // 에라토스테네스의  체를 이용하여 개수를 구한다.
    cout << Eratos(arr, M, N) << endl;
 
    delete[] arr;
}
 
int Eratos(int* arr, int M, int N)
{
    // 소수의 개수
    int cnt = 0;
 
    for (int i = 0; i < N; ++i)
    {
        // 합성수인 경우 제외함 + 1은 소수도 합성수도 아니니 제외
        if (arr[i] == COMPOSIT) continue;
 
        // 소수를 찾은 경우 범위 내에 있는 경우 개수 증가
        if (arr[i] >= M ) cnt++;
 
        // 합성수가 아닌 가장 작은 수는 소수라고 판단
        // 배수를 판단하기 위해 현재 수를 저장
        int num = arr[i];
        arr[i] = PRIME;
 
        // 이 소수의 배수들은 합성수이므로 제외
        for (int j = i + num; j < N; j += num)
        {
            arr[j] = COMPOSIT;
        }
    }
    
    return cnt;
}

 

 

JUNGOL) 문제은행) 실력키우기) 소수의 개수