백준 1929번, 소수 구하기

백준 1929번 c++ 문제풀이

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

풀이:

어떤 수가 소수인지 판별 하기 위해서는 어떤 수 n의 제곱근을 구한 후, n을 2부터 제곱근 까지의 숫자로 나눴을 때에 나눠지면 소수가 아닌 것이다.

코드:

#include <iostream>
#include <math.h>

using namespace std;

bool findprime(int a){
    if(a == 1){
        return false;
    }
    else if(a >= 2){
        int s = sqrt(a);
        for(int j=2; j<=s; j++){
            if(a % j == 0){
                return false;
            }
        }
    }

    return true;
}

int main(){
    int m, n;

    cin >> m >> n;

    for(int i=m;i<=n;i++){
        if(findprime(i)){
        cout << i << "\n";
        }

    }
    

    return 0;
}

소수 구하는 조건에 맞는 판별 함수를 만들어 주고 풀면 된다. 소수 판별할 수 있는 방법을 알면 풀 수 있다.