백준 1929_소수 구하기.cpp

<소스코드>

#include <iostream>
#include <cmath>
using namespace std;
int main(){
    int M, N;
    cin >> M >> N;
    int arr[N-M+1] = {0,}; 
    int CheckList[N-M+1] = {0, }; // 배운점
    for(int i = 0; i < N-M+1; i++){
        arr[i] = M+i;
    }
    for(int j = 2; j <= sqrt(N); j++){ //배운점
        for(int i = 0; i < N-M+1; i++){
            if(CheckList[i] == 0){
                if(arr[i]%j == 0 && arr[i] != j){
                    CheckList[i] = 1;
                    
                }
            }
        }
    }

    for(int k = 0; k < N-M+1; k++){
        if(CheckList[k] == 0 && arr[k] != 1){
            cout << arr[k] << '\n'; //배운점
        }
    }
    return 0;
}

1. 변수
   int M, N : 입력받은 두 수(m이상 n이하)
   int arr[N-M+1] : M과 N사이에 정수들의 배열
   int CheckList[N-M+1] : M과 N사이에 정수들 중 소수인지 판단하는 배열

2. 알고리즘
   1) arr에 M과 N사이의 정수들을 입력한다.
   2) j를 2부터 N의 제곱근까지 돌리면서 만약 CheckList가 0이면(아직 검사를 안 했음 혹은 지금까지 다 통과함) arr[i]와 j가 나누어 떨어지되 j가 아니라면 CheckList의 값을 1로 변경한다.
   3) ChekList 반복문을 돌면서 0인 경우이되, 1이 아니라면 출력해준다.

3. 배운점
   1) 배열 0으로 초기화 : 타입 배열이름 = {0, }
   ex) int CheckList[N-M+1] = {0, };
   2) 소수판별 범위 설정법
   - 2부터 비교하려는 대상 전까지 (2~N-1)
   - 해당 숫자의 절반까지만 비교
   why? 자기자신을 제외하고 절반을 초과하는 숫자에서 나눴을 때 나머지가 0인 숫자가 나올 수 없음(2~2/N)
   - 해당 숫자의 제곱근까지 확인하는 방법
   why? 어떤 수 n이 소수가 아닌 경우 n = a * b 관계이므로 n을 a나 b로 나눠 보면 된다. a와 b 중 더 큰 수는 무조건 n의 제곱근의 값보다 크다. (더 작은 수는 n의 제곱근 이하의 값을 가진다.)
   즉, 어떤 정수 n의 제곱근까지의 수 중 한 개의 수에 대해서라도 나누어떨어지면 소수가 아니다.
   3) 시간초과가 나면 endl을 '\n'으로 바꿔보자!

4. 아쉬운점&느낀점
   시간초과가 정말로 많이 나던 문제였고, 이 문제를 시작으로 소수의 지옥에 빠지게 되었던거 같다. 그렇지만 포기하지 않고 개념을 잘 이해한 나 자신에게 칭찬하는데 오늘 왜이렇게 졸리냐...ㅠㅠ