소수의 개수

소수의 개수

문제

소수(prime number)란 1보다 큰 자연수 중 1과 자기 자신 두 개만을 약수로 갖는 수를 말한다.

자연수 M과 N을 입력받아 M부터 N까지 소수의 개수를 구하여 출력하는 프로그램을 작성하시오.

 

입력형식

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

 

출력형식

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

 

입력 예

10 100

 

출력 예

21

 

 

Hint!

코드1

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

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 log 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 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

int prime[2000005];   void eratos(int n) {     int i, j;     prime[0]=​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로 바뀌어 있다.

 

1 2 3

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

 

 

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

 

1 2 3

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