백준_1929 : 소수 구하기 - C++

문제

---

문제 해석

- 주어진 숫자 사이에 존재 하는 소수를 구하여 출력 하면 되는 문제이다.

---

알고리즘

- 주어진 범위의 모든 수num 을 2부터 num 의 제곱 근 까지 나누어 보면서 하나라도 나누어 지는 수가 있다면 소수가 아니다.

- 그렇지 않으면 소수이기 때문에 출력 하면 된다.

- 이때 num 의 제곱근까지만 나누어 보는 이유는 제곱근 보다 큰 수는 결국 제곱근 보다 작은수와 곱해서 num 을 만들기 떄문이다.

- 즉 제곱근 보다 작은 수로도 나누어 지지 않았다면 제곱근 보다 큰 수로도 나누어 지지 않는다.

---

코드

#include <iostream>
using namespace std;

bool CheckPrime(int num){
    bool result = true;
    if(num == 1){
        result = false;
    }
    for(int i = 2; i*i <= num; i++){
        if(num % i == 0){
            result = false;
            break;
        }
    }
    return result;
}

int M, N;
int main(){
    cin >> M >> N;
    for(int i = M; i <= N; i++){
        if(CheckPrime(i)){
            cout << i << '\n';
        }
    }
    return 0;
}