[BOJ-2581][C++] 소수

문제

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

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

 

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

 

출력

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

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

 

예제 입력 1

60
100

 

예제 출력 1

620
61

 

예제 입력 2 

64
65

 

예제 출력 2 

-1

 

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2006 > 중등부 1번

 

알고리즘 분류

• 수학
• 정수론
• 소수 판정

 

문제 출처

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

2581번: 소수

 

문제 해결 방법

• 소수 찾기 알고리즘을 이용하여 문제를 해결하였다.
• 더불어 벡터 STL을 발견한 소수를 삽입하고 오름차순으로 정렬하는데 사용하였다.

 

코드

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

int M, N, sum, minNum, cnt, prime;
vector<int> primeNums;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> M;
    cin >> N;

    sum = 0;
    cnt = 0;
    for (int i = M; i <= N; i++) {
        prime = 0;
        for (int j = 1; j <= i; j++) {
            if (i % j == 0) {
                prime++;
            }
        }
        if (prime == 2) {
            cnt++;
            sum += i;
            primeNums.push_back(i);
        }
    }

    if (cnt) {
        sort(primeNums.begin(), primeNums.end());    // 오름차순 정렬
        minNum = primeNums[0];
        cout << sum << '\n' << minNum << '\n';
    }
    else {
        cout << "-1" << '\n';
    }

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [기본 수학 2]
• 실버V