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

# 문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

 

 

---

 

# 풀이

지난 번에 풀이한 소수 코드를 잘 풀었다면 금방 해결할 수 있는 문제다.바로 정답 소스코드를 확인해보자.

 

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

int main(){
    vector<int> prime;
    int primeSum = 0;
    bool primeCnt = 0;
    int m, n;
    cin >> m >> n;
    
    for(int i=m; i<=n; i++){
        bool primeNum = 1;
        if(i == 1) continue;

        // 소수인지 확인
        for(int j=2; j<i; j++){
            if(i%j == 0){
                primeNum = 0;
                break;
            }
        }
        // 소수라면 소수 vector에 추가하고 합 구하기
        if(primeNum){
            prime.push_back(i);
            primeSum += i;
            primeCnt = 1;
        }
    }
    
    if(!primeCnt) cout << "-1"; // 확인한 수 중 소수가 하나도 없다면
    else cout << primeSum << '\n' << prime.front();
    return 0;
}

M과 N 사이에 소수가 몇 개 있는지 모르니까 소수를 담을 공간을 vector로 만들어주었다.

그리고 소수의 합을 확인할 int 타입 primeSum, 소수가 하나도 없는지 확인해줄 bool 타입 primeCnt을 만들고 for문으로 M과 N 사이를 탐색!

 

 

 

 

for(int i=m; i<=n; i++){
    bool primeNum = 1;
    if(i == 1) continue;

    // 소수인지 확인
    for(int j=2; j<i; j++){
        if(i%j == 0){
            primeNum = 0;
            break;
        }
    }
    // 소수라면 소수 vector에 추가하고 합 구하기
    if(primeNum){
        prime.push_back(i);
        primeSum += i;
        primeCnt = 1;
    }
}

for문 안에서는 소수인지 아닌지 확인해줄 bool 타입 변수를 primeNum으로 하나 만들어주고 탐색을 진행한다.

만약 입력된 숫자가 1이라면 1은 소수가 아니므로 continue로 다음 탐색을 진행하고 아니라면 다음의 단계를 진행한다.

지난 번에 풀이했던 로직을 참고해서 소수인지 아닌지 확인해주고, 소수가 아니라면 primeNum을 false로 변경하고 반복문을 탈출한다.

만약 primeNum가 여전히 true라면 해당 수는 소수이므로 소수 벡터에 넣고 합계에도 더해준다. 그리고 소수가 존재함을 확인하는 변수인 primeCnt를 true로 변경!

 

 

 

if(!primeCnt) cout << "-1"; // 확인한 수 중 소수가 하나도 없다면
else cout << primeSum << '\n' << prime.front();

마지막으로 primeCnt를 통해 소수가 존재하는지 확인하고 존재하지 않는다면 -1을 출력, 존재한다면 합계와 소수 벡터의 가장 첫번째 값을 출력해주면 정답이다.

 

 

 

 

 

 

---

 

 

 

2581번: 소수