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

문제 이해하기

이전에 푼 백준 1978번(소수찾기) 문제와 마찬가지로 소수 찾기 알고리즘으로 풀면 된다. 다만 그 문제와 다른 점은 소수의 개수가 아닌, 소수들의 합과 그 중 가장 작은 값을 출력해야한다는 것이다. 

 

코드로 표현하기

#include <iostream>

using namespace std;

bool isit(int x) {
	if (x < 2 ) return false;
	for (int i = 2; i < x; i++) {
		if (x % i == 0) return false;
	}
	return true;

}

int main() {
	int m, n;
	cin >> m >> n;

	int min = n;
	int sum = 0;
	for (int i = m; i <= n; i++) {
		if (isit(i)) {
			if (min > i) min = i;
			sum += i;
		}
	}
	if (sum == 0) cout << -1;
	else cout << sum << endl << min;
}

1978번 풀 때 정의했던 소수 점검 함수를 그대로 이용했다.

1978번과 다른 점은 main 안의 for문이다. 일단 그때와는 달리 m에서 n까지의 자연수를 점검하므로 반복문의 범위를 다르게 하였다. 또 소수 점검 함수를 통해 구한 결과가 true라면, 즉 해당 자연수가 소수라면, min값과 비교하여 작은지 확인하고 작다면 값을 갱신해준다(min의 초깃값은 n). 또한 sum값에 해당 소수를 더해주어 합을 계산한다.

마지막으로 문제에서 m이상 n이하의 자연수 중 소수가 없다면 -1을 출력하라고 하였으므로 if문으로 소수 존재 여부 확인(sum값이 0인지, 아닌지로 점검)하고 결과를 출력한다.