백준 2581번 (소수) c++

문제

문제풀이

이 문제는 에라토스테네스의 체만 안다면 쉽게 풀 수 있는 문제다.

 

에라토스테네스의 체는

1 ~ 120 까지 나열을 한뒤 

 

1. 1은 소수가 아니기 때문에 제외한다.

2. 2의 배수 중 2는 소수이기 때문에 남기고 나머지는 제외한다. (빨간색)

3. 3의 배수 중 3은 소수이기 때문에 남기고 나머지는 제외한다. (초록색)

4. 5의 배수 중 5는 소수이기 때문에 남기고 나머지는 제외한다. (파란색)

5. 7의 배수 중 7은 소수이기 때문에 남기고 나머지는 제외한다. (노란색)

6. 위 과정을 반복한다.

 

이렇게 먼저 N까지 소수를 판별한뒤 답을 출력하면 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int prime[10001];

int main(){

        ios_base::sync_with_stdio(false);
        cin.tie(0);

        int M, N;

        cin >> M >> N;

        prime[0] = prime[1] = 1;


        for(register int i = 2; i <= N; i++){

                if(prime[i]) continue;

                for(register int j = i*2; j <= N; j+=i){
                        prime[j] = 1;
                }

        }

        int sum = 0, small = -1;

        for(register int i = M; i <= N; i++){
                if(!prime[i]){
                        sum += i;

                        if(small == -1){
                                small = i;
                        }
                }
        }

        if(small == -1){
                cout << small << '\n';
        }
        else{
                cout << sum << '\n' << small << '\n';
        }


        return 0;

}