[백준 / BOJ] - 2581번 소수 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [2581] 

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

문제

 

숫자 M과 N을 받아서, M이상 N 이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에는 그 합을, 둘째 줄에는 최솟값을 출력하는 프로그램을 작성하는 문제이다. 이 때 소수가 없는 경우엔 -1을 출력한다.

 

풀이

 

에라토스테네스의 체를 활용하여 Max값 까지 존재하는 소수들을 모두 구하고, 합과 최솟값을 구하면 되는 문제이다.

에라토스테네스의 체를 개념을 구현하여 구하고자하는 소수 범위의 재곱근보다 작은 소수들의 배수들을 모두 지워나가다보면 마지막에 남는 수는 모두 소수라는 사실을 이용한 풀이 방식으로 접근하면 쉽게 풀이가 가능하다.

코드

 

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

int main() {
    int min,max,sum = 0;
    int min_value;
    bool prime[10000];
    fill_n(prime, 10000, 1);
    prime[0] = false;
    prime[1] = false;
    cin >> min;
    cin >> max;
    for (int i = 2; i <= sqrt(max); i++)
        if(prime[i] == true)
            for(int j = i*2; j <= max; j += i)
                prime[j] = false;

    for (int i = min; i <= max; i++)
        if(prime[i] == true)
        {
            if(sum == 0)
                min_value = i;
            sum += i;
        }
    if(sum == 0)
        cout << "-1";
    else
        cout << sum << '\n' << min_value;
    return 0;
}

 

평가

 

에라토스테네스의 체 개념을 모르는 사람에게는 다소 생소하고 어려울 수 있는 문제이다.

정답률은 39%지만 에라토스테네스의 체를 활용하기만 한다면 어렵지 않게  금방 풀 수 있다.