관리 메뉴

Bull

[백준] 2581: 소수 (C++) 본문

Algorithm/Baekjoon

[백준] 2581: 소수 (C++)

Bull_ 2024. 2. 24. 13:46

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

 

2581번: 소수

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.  단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

www.acmicpc.net

 

 

 

 

 

요구사항

① 첫 째줄, 두 째줄에 시작하는 숫자(Min)와 끝나는 숫자(Max)를 적어준다.

② Min이상 Max이하의 숫자 중 소수들의 합과 최솟값을 구해준다.

③ 만약 소수가 없으면 -1을 출력한다.

 


주의사항

-

 

 

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int min, max;
    int sum = 0;
    int prime_m;
    cin >> min >> max;

    // 에라토스테네스 체
    vector<bool> prime(max + 1, true);
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i <= max; i++) {
        if (prime[i]) {
            for (int j = i + i; j <= max; j += i) {
                prime[j] = false;
            }
        }
    }
    // min 1개만 구하기
    for (int i = min; i <= max; i++) {
        if (prime[i]) {
            prime_m = i;
            min = i;
            sum += prime_m;

            break;
        }
    }
    // sum 구하기
    for (int i = min + 1; i <= max; i++) {
        if (prime[i]) {
            sum += i;
        }
    }

    if (sum)
        cout << sum << endl << prime_m;
    else
        cout << -1;

    return 0;
}

 

 

 

 

 

 

1. 에라토스테네스의 체
    // 에라토스테네스 체
    vector<bool> prime(max + 1, true);
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i <= max; i++) {
        if (prime[i]) {
            for (int j = i + i; j <= max; j += i) {
                prime[j] = false;
            }
        }
    }

 

에라토스테네의 체는 정해진 범위 내에서 소수를 구하는 방법 중 하나이다.

 

모든 자연수 중에서 1과 자기 자신만을 약수로 하는 수(소수)를 구하는 것은 다른 방식으로 1과 자기 자신을 제외한 그 수의 배수들을 모두 지우면 된다.

 

예를 들어, 숫자 2를 검사할 때 1과 2를 제외한 4,6,8.... 은 소수가  아니라고 판정할 수 있다.

 

차례대로 3,4,5,6의 자기 자신을 제외한 배수들을 범위 내에서 지워주면 된다.


vector를 이용해 숫자에 대해 소수인가 아닌가의 판별성을 부여해준다.

0은 자연수가 아니니 false 이고,

1은 소수가 아니니 false이다.

 

index는 0부터 이니 max+1을 부여해 자연수(index)의 범위는 1~max가 된다.

 

나머지 vector의 bool값은 위의 에라토스테네스 체 방식을 이용해 판별해준다.

 

 

 

2. 소수의 최소값 구하기
    // min 1개만 구하기
    for (int i = min; i <= max; i++) {
        if (prime[i]) {
            prime_m = i;
            min = i;
            sum += prime_m;

            break;
        }
    }

 

우선적으로 처음 소수를 발견하면 break를 통해 반복문을 종료하고 다음 반복문을 실행하면된다.

 

주의할점은 다음 검사 숫자(i)를 1올려주어야 한다.

 

그리고 소수의 합을 구하는 sum 변수에 소수를 더해준다.

 

 

 

 

 

3. 모든 소수의 합

 

    // sum 구하기
    for (int i = min + 1; i <= max; i++) {
        if (prime[i]) {
            sum += i;
        }
    }

 

 

 

 

 

 

4. 출력
    if (sum)
        cout << sum << endl << prime_m;
    else
        cout << -1;

    return 0;

 

만약 Min과 Max 사이에 소수가 없으면 sum은 0이 되니 조건과 같이 -1을 출력해준다.