[Inflearn] 소수의 개수

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 우선 최대 N이 200,000 이므로 이중 반복문으로 그냥 풀면 N^2 = 40,000,000,000 이 되어 시간초과가 날 것이다.

    소수를 구하는 방법은 흔히 3가지 방법이 있다.

      - 기본 : 2 ~ (N-1) 까지 수로 나누어지지 않는지 확인

      - 에라토스테네스 : N ~ sqrt(N) 까지 수로 나누어지지 않는지 확인

      - 에라토스테네스의 체  : 2 ~ (N -1) 까지 배수를 모두 체로 거르는 방법

  2. 해당 문제는 N 까지의 소수의 개수를 구해야 하므로 에라토스테네스의 체로 접근하는 것이 적절할 것 같다.

#. Code

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

#include <cstdio> #include <cmath>   bool isNotPrm[200001];   int main() {     freopen("input.txt", "rt", stdin);     int n, i, j, cnt = 0;       scanf("%d", &n);       for (i = 2; i <= n; i++)     {         if (isNotPrm[i] == false)         {             for (j = i * 2; j <= n; j += i)                 isNotPrm[j] = true;         }     }       for (i = 2; i <= n; i++)     {         if (isNotPrm[i] == false)             cnt++;     }       printf("%d\n", cnt);       return 0; } Colored by Color Scripter

cs

#. Other code

#include<stdio.h>            
 
int main(){
    int n, i, j, flag, cnt=0;
 
    scanf("%d", &n);
 
    for(i=2; i<=n; i++){
        flag=1;
 
        for(j=2; j*j<=i; j++){
            if(i%j==0){
                flag=0;
 
                break;
            }
        }
 
        if(flag==1) cnt++;
    }
 
    printf("%d\n", cnt);
 
    return 0;
}

여기서는 두 번째 에라토스테네스 방법을 사용한 것 같다.

흥미로운 것은 sqrt 함수를 사용하지 않고, (line 11) j 를 제곱하면서 sqrt 와 같은 효과를 냈다.

내 코드는 (2 ~ N) * 2 번 반복하였고, 위 코드는 (2 ~ N) * (2 ~sqrt(n)) 번 반복하였다.

에라토스테네스의 체로 접근한 방법이 약간 더 빠른 것 같긴 하다.. 비교해보았을 때 비슷하긴 하지만..

여기서, 왜 제곱근까지만 확인해도 되냐면

36 이 소수인지 판별하기 위하여, 36의 약수를 확인해보자.

1 X 36

2 X 18

3 X 12

4 X 9

6 X 6 

여기서 36의 제곱근 6까지만 확인하면 num이 약수가 있는지 없는지를 알 수 있는 것이다.

36의 약수에 2가 포함된다면 18도 36의 약수일 것이고, 3이 포함된다면 18도 약수일 것이다.

결국 1 ~ sqrt(num) 까지만 확인해도 num 이 소수인지 아닌지 판별할 수 있다.

다른 수로 26도 적용해보자.

1 X 26

2 X 13

여기도 마찬가지로 26의 제곱근 5까지만 확인해도 26이 소수인지 아닌지 판별 가능하다.

#. Result

  - Input --------------------------------------------------------

20

------------------------------------------------------------------

  - Output --------------------------------------------------------

8

------------------------------------------------------------------