알고리즘(C++) / 백준 2581 : 소수

2581

www.acmicpc.net/problem/2581

2581번: 소수

 

문제

자연수 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을 출력한다.

 

코드

//2581 소수
#include <iostream>
using namespace std;

int main() {
	int M, N;
	int sum = 0, min;

	cin >> M >> N;

	int check_prime;
	int check_min = 0;
	for (int i = M; i <= N; i++) {
		if (i == 1)
			continue;
		check_prime = 0;
		for (int j = 2; j < i; j++) {
			if (i % j == 0) {
				check_prime = 1;
				break;
			}
		}
		if (check_prime == 0) {
			sum += i;
			check_min++;
			if (check_min == 1)
				min = i;
		}
	}

	if (sum == 0)
		cout << "-1" << endl;
	else
		cout << sum << endl << min << endl;

	return 0;
}

 

결과 

 

설명

자연수 M과 N을 입력받아 그 사이 소수의 합과 가장 작은 소수를 출력하는 문제이다.

소수의 합은 sum으로 가장 작은 소수는 min으로 입력받고, 소수인지 확인하기 위해 check_prime과 가장 작은 소수 확인을 위해 check_min을 선언해주었다.

M부터 N까지 반복하여 소수를 찾는다. 소수는 1과 자기 자신 이외에는 나누어 떨어지지 않는 수이다. 따라서 1 초과 자기 자신 미만까지 나눠보면서 나눠 떨어지면 chck_prime = 1으로 소수가 아니라는 것을 판단할 수 있다. check_prime이 0일 때만 소수라 판단하여 sum에 더해준다.

가장 작은 소수는 소수를 찾을 떄마다 check_min에 +1을 해주고 check_min이 1일 때 min값을 저장한다.

출력할 때 sum == 0이라면 M과 N사이의 소수가 없다는 의미이므로 -1을 출력해주게 된다.

1일 때는 소수가 아니므로 예외 처리해줄 필요가 있다.

 

마지막에 멍청하게.. else를 해주지 않아서 틀렸었다..