[BOJ/백준] 2581번 소수 C++ 문제 풀이

단계별로 풀어보기 - 수학 2단계 - [2단계] 2581번

문제

문제 링크 : www.acmicpc.net/problem/2581

2581번: 소수

입력 복사 : 

> 예제 입력 1

60 100

>예제 입력 2

64 65

 

풀이

소수를 판별하는 방식은 이전 단계인 1978번에서와 동일하당.

일단 소수일 때는 소수의 합을 저장하는 sum에 해당 변수를 더해준다.

 

또, 소수를 구할 때 M부터 작은 순서대로 소수 여부를 검사하기 때문에

min값이 저장된 값이 없음을 나타내는 초기값 -1인 경우에 처음으로 등장한 소수가 최소인 소수이다.

이 최소인 소수를 min에 저장하면 된다!

 

만약 주어진 M~N범위에서 소수가 나타나지 않을 경우 min값이 초기값 그대로 -1일 것이기때문에

최종 결과를 출력하기 전, min값을 -1인지 체크하고 결과를 출력한다.

 

CODE

#include <iostream>
using namespace std;

int main() {
	int M, N;
	int sum = 0, min = -1;
	int cnt = 0;
	cin >> M >> N;

	for (int i = M; i <= N; i++) {
		for (int div = 1; div <= i; div++) {
			if (i%div == 0)
				cnt++;
		}
		if (cnt == 2) {		//i가 소수일 때
			if (min == -1)		//저장된 소수의 최솟값이 없을 때
				min = i;
			sum += i;
		}
		cnt = 0;
	}
	if (min == -1)
		cout << -1 << '\n';
	else
		cout << sum << '\n' << min << '\n';
}

 

결과