백준 2581번 C++ 소수 판별하기

소수 판별하고 최솟값, 합 출력하기

https://www.acmicpc.net/problem/2581

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

 

코드

#include <iostream>
#include <math.h>
using namespace std;

bool isPrime(int n) {
    if(n<=1) {
        return false;
    }

    for(int i=2; i<=sqrt(n); i++) {
        if((n%i)==0) {
            return false;
        }
    }

    return true;
}

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

    int min = M;
    int sum = 0;

    while (M <= N) {
        if(isPrime(M)) {
            min=M;
            break;
        }
        M++;
    }

    while (M <= N) {
        if(isPrime(M)) {
            sum+=M;
        }
        M++;
    }

    if(sum!=0) {
        cout<<sum<<"\n"<<min;
    } else {
        cout<<-1;
    }

    return 0;
}

소수를 판별할 때 해당 수의 제곱근까지만 검사해도 소수 여부를 판별할 수 있다.

n이 1보다 같거나 작으면 소수가 아니므로 return false

n의 제곱근보다 작고 2보다 크거나 같은 수 i로 n%i를 조사해서 하나라도 0이 나온다는 것은

n이 i의 배수라는 뜻이므로 return false

결국 저 함수들이 멈추지 않고 다 돌 때만 true를 리턴하는 게 isPrime 함수다.

맨 처음에 최솟값을 찾는데 최댓값과 다르게 최솟값은 계속 갱신해 줄 필요가 없다.

따라서 찾는 즉시 break

그 다음 while문에서는 합을 출력하는 건데 isPrime이 true 일 때만 더하므로 sum은 소수들의 합이 된다.

그리고 나서 출력해주면 되는데 백준 문제 풀 때 C++에서는 endl보다 "\n"이 효율적이다.