[Baekjoon/C++] 소수 구하기 1929번

Baekjoon Online Judge

문제로 이동

 

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

---

예제 입력	예제 출력
3 16	3 5 7 11 13

---

풀이

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int M, N;
    cin >> M >> N;

    // M부터 N 혹은 N까지의 숫자 중에서 소수를 찾는다.
    for (int i = M; i <= N; i++) {
        if (i == 2 || i == 3) 
            printf("%d\n", i);
        
        // 짝수는 소수가 될 수 없다.
        if (i % 2 == 0) continue;

        int num = sqrt(i);
        for (int j = 2; j <= num; j++) {
            // 소수는 자기자신과 1만으로만 나누어 떨어져야한다.
            if (i % j == 0) break;
            
            // 소수를 찾으면 출력
            if (j == num)
                printf("%d\n", i);
        }
    }

    return 0;
}