백준 2581 (C++) 소수

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

다양한 풀이가 있는 것 같아 내 것도 올려본다.

 

제곱근

 

소수가 아닌 N의 약수는 무조건 [1,N] 사이에 존재한다.

어떤 자연수 n이 소수인지 알기 위해서 제곱근 n까지만 진행하면 된다.

수가 수를 나누기 위해서 몫이 항상 필요하며 나누는 수와 몫 중 하나는 반드시 제곱근n 이하이기 때문이다.

나누는 수와 몫이 제곱근n을 좌우로 대칭이므로 제곱근값보다 같거나 작은 숫자로 나누어지면 그 이후는 계산을 할 필요가 없다.

때문에 계산이 간략해진다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
const int INF = 10001;
int ans = 0;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n,m, prime_min = INF;
    cin >> m >> n;
    for (int i = m; i <= n; i++) {
        if (isPrime(i)) {
            prime_min = min(i, prime_min);
            ans += i;
        }
    }
    if (prime_min == INF) { // 소수의 최솟값이 없는 경우 == 소수가 없는 경우
        cout << "-1";
        return 0;
    }
    cout << ans << '\n' << prime_min;
    return 0;
}