실력키우기 소수의개수(JAVA)

2813 : 소수의 개수

제한시간: 1ms    메모리제한: 128MB
해결횟수: 382회    시도횟수: 1558회   

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

 

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

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

[Copy] 10 100

[Copy] 21

?

1. /**************************************************************
2.     Problem: 2813
3.     User: a132034
4.     Language: Java
5.     Result: Success
6.     Time:1220 ms
7.     Memory:16684 kb
8. ****************************************************************/
9.  
10.  
11. import java.util.Scanner;
12.  
13. public class Main
14. {
15.     public static void main(String[] args) {
16.         final int UNDEFINE = 0;
17.         final int PRIME = 1;
18.         final int NOT = 2;
19.  
20.         Scanner sc = new Scanner(System.in);
21.         int min = sc.nextInt();
22.         int max = sc.nextInt();
23.  
24.         int count = 0;
25.         boolean minFlg = true;
26.  
27.         int[] arr = new int[max+1];
28.         arr[1] = NOT;
29.         for(int i = 2; i <= max; ++i)
30.         {
31.             boolean isPrime = true;
32.             if(arr[i] == UNDEFINE)
33.             {
34.                 for(int j = 2; j*j < i; ++j)
35.                     if(i % j == 0)
36.                         isPrime = false;
37.  
38.                 if(isPrime){
39.                     arr[i] = PRIME;
40.                 }
41.                 if(i < Math.sqrt(max)){
42.                     for(int j = i*i; j <= max; j = j+i)
43.                         arr[j] = NOT;
44.                 }
45.             }
46.         }
47.  
48.  
49.         for(int i = min; i <= max; ++i)
50.         {
51.             if(arr[i] == PRIME)
52.                 count ++;
53.         }
54.         System.out.println(count);
55.     }
56. }

바로 이전 포스팅인 소수구하기를 그대로 적용시켜보았다. 

결과는 7개정도 통과, 나머지 타임아웃. 

도움말을 보며 원인 분석을 시작..

도움말을 보다 보니 내 코드와 결정적으로 다른 두 가지를 알게 됨. 

1. 기존의 코드에서는 모든 수를 돌며 모든 수의 배수를 소수가 아닌 것으로 해 주었음 

-> 해당하는 수의 이전까지는 모두 이미 걸러내어져 있기 때문에 중복하는 경우가 생김 

ex) 2일 때 걸러낸 경우 -> 4, 6, 8, 10... 을 모두 걸러냄

이후 3일 때 걸러내는 경우 -> 6, 9, 12.. 중 6은 이미 위에서 걸러내었기 때문에 중복된 경우가 생김. 

이를 확인해 보면 i일 때 i*i의 전 까지 (3일 때 3*3 = 9)는 이미 걸러내어져 있다. 

이유는 j를 걸러낼 때에 j보다 작은 수를 곱해서 나오는 값들은 이미 걸러져 있기 때문. 

ex) 10을 걸러낼 때에 10*9, 10*8, 10*7 ... 10*2 는 모두 2, 3, 4, 5, 6, 7, 8, 9에서 걸러내졌기 때문. 

때문에 걸러낼 때 해당 수의 배수부터 시작해서 걸러내 준다. 

-> 이는 결국 해당 수의 배수가 max값이 되기 전 까지만 실행하면 된다는 결론을 얻을 수 있다. 

ex) 1부터 2500까지를 구할 경우 

50의 제곱(50*50)은 2500이므로 50이후의 숫자부터는 걸러낼 필요가 없다. 

2. 두 번째로  for(int j = 2; j*j < i; ++j)

소수를 체크하는 루프의 조건을 j < i 에서 j*j < i로 바꾸었다. 

이는 j*j > i 가 되는 j부터는 체크할 필요가 없다는 말인데 

이 식은 잘 이해를 못하겠어서 찾아보았더니..

이미 수학에서 증명된 공식이라고 한다. 

소수는 1과 자기자신을 제외한 수의 배수가 아니어야 하기 때문에 현재값 i를 확인 할 때 이 수보다 작은 수들로 나누어서 떨어지면 소수가 아닌것이다. 라는게 기본적인 소수의 정의이지만

루트i 까지만 나누어서 나누어 떨어지면 소수가 아니라고 수학적으로 증명되었다. 

코드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