[01929] 소수 구하기

Byeongmin·2021년 6월 8일

단계별로 풀어보기 백준

백준 단계별로 풀어보기

목록 보기

10/69

[01929] 소수 구하기

문제

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

입력

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

출력

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

코드

#include <iostream>

using namespace std;

/* 함수 */
// 3 이상의 홀수 num에 대하여 소수인지 판별
bool isPrimeNum(int num) {
    for(int i = 3; i * i <= num; i += 2) { // √num 까지만 확인
        if(num % i == 0) return false; // 소수가 아닌 경우 false 반환
    }
    return true; // 소수인 경우 true 반환
}

int main() {
    int M, N;

    scanf("%d%d", &M, &N);

    if(M == 1) M++;

    if(M == 2 && N > 1) {
        printf("%d\n", 2);
        M += 1;
    }

    if(M % 2 == 0) M++;

    for (int i = M; i <= N; i += 2) {
        if(isPrimeNum(i)) printf("%d\n", i);
    }
}