[백준] 2581번 : 소수 | C++

1. 문제 상세

 

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

 

 

 

2. 문제 접근

 

주어진 수 M 부터 N 까지의 자연수 중 소수를 찾자.

범위 내의 소수를 찾기 위해 에라토스테네스의 체 알고리즘을 사용하여 문제를 해결해보자.

 

■ 에라토스테네스의 체

출처 : 위키백과

에라토스테네스의 체 알고리즘은 주어진 범위 내에서 소수들을 찾는데 효율적인 알고리즘이다.

 

2부터 주어진 수 까지의 수들 중 가장 작은 수의 배수부터 지워나간다.

가장 작은 수의 제곱이 주어진 수보다 작을 때 이 과정을 반복한다.

 

위 사진에서는 2부터 120까지의 수가 있다.

가장 먼저 2부터 120까지의 2의 배수가 모두 지워지고, 그 다음 3의 배수가 모두 지워진다.

그 다음 지워지지 않은 수 중 가장 작은 수인 5의 배수, 그 다음 7의 배수가 지워진다.

그 다음의 수는 11이 되는데 11² > 120 이므로 배수를 지우는 과정을 끝낸다.

이제 남은 수들이 2부터 120까의 소수들이다.

 

위의 에라토스테네스의 체 알고리즘을 활용하여 N 까지의 소수들을 확인하고

소수들 중 M 이상 N 이하인 수만 찾아서 모두 더하고, 그 수중 가장 작은 수를 찾자.

범위 내에 소수가 없는 경우 -1을 출력하자.

 

 

 

3. 문제 풀이

 

#include <iostream>
using namespace std;

int main() {
    int n, m, sum = 0, min = -1;
    bool num[10001] = { true, true, false, };
    
    cin >> m >> n;
    
    for(int i = 2; i * i <= n; i++) {
        if(num[i]) continue;
        for(int j = 2; i * j <= n; j++) num[i * j] = true;
    }
    
    for(int i = m; i <= n; i++) {
        if(!num[i]) {
            sum += i;
            if(min == -1) min = i;
        }
    }
    
    if(sum != 0) cout << sum << endl << min;
    else cout << "-1";
}

 

정수형 변수 n, m, sum, min 을 선언하고 sum 은 0으로, min 은 -1 로 초기화한다.

크기가 10001인 bool(참 거짓형)형 배열 num 을 선언하고 0, 1번 인덱스의 값을 true 로, 나머지 값을 false 로 초기화한다.

 

cin 으로 정수 두개를 입력받아 각각 m 과 n 에 저장한다.

 

for문으로 i 가 2부터 i 의 제곱값이 n 보다 작거나 같을 때 i 에 1씩 더하며 반복하도록 한다.

if문으로 num 의 i 번 인덱스의 값이 true 라면 continue 로 이번 반복을 건너뛰도록 한다.

for문을 사용하여 j 가 2부터 j 와 i 를 곱한 값이 n 보다 작거나 같을 때 j 에 1씩 더하며 반복한다.

num 의 j x i 번 인덱스의 값을 true 로 바꾼다.

 

위 반복이 모두 끝나면 for문으로 i 가 m 부터 n 보다 작거나 같을 때 i 에 1씩 더하며 반복하도록 한다.

if문으로 num 의 i 번 인덱스의 값이 false 면 sum 에 i 의 값을 더하고,

if문으로 min 이 -1인 경우 min 에 i 를 저장한다.

 

위 반복이 끝나면 if문으로 sum 이 0이 아닌 경우 cout 으로 sum 과 min 을 출력하고,

그 외에 cout 으로 -1을 출력한다.

 

 

 

4. 성능 확인

 

 

 

 

5. 마무리

 

이전에 풀어본 문제 1978 : 소수 찾기 를 해결해 보고 다음엔 에라토스테네스의 체 알고리즘을 사용해보려 했었는데

이렇게 바로 다음 문제에 활용하게 될 줄은 몰랐다.

 

소수 판별 문제에서 유용하고 효율적으로 사용 가능한 알고리즘이니 잘 알아두자.