[Baekjoon-2581번][C++] 백준 소수

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

---

풀이

Algorithm

1. 변수 설명
   1. M, N : 수의 범위를 나타냅니다.
   2. min : 주어진 범위 중 가장 최소인 소수를 저장합니다. / for문을 돌 때마다 계속 더 작은 소수가 덮어써집니다.
   3. sum : 주어진 범위에 있는 모든 소수를 합한 결과를 저장합니다. / 처음에는 0으로 초기화 해줘야 해요!
   4. flag : 주어진 범위에 소수가 있는지 판단하는 변수입니다. 소수가 있으면 true, 없으면 false를 저장합니다. / 처음에는 false로 초기화 해줘야 해요!
2. is_prime 함수 설명
   1. 입력 받은 수가 소수이면 true를, 아니라면 false를 return하는 함수입니다.
   2. 입력으로 받은 수가 1이거나 2가 아닌 짝수라면 우선 false를 return해줍니다.
   3. 그게 아니라면 자신의 루트값보다 작거나 같고, 1이 아닌 홀수들로 차례로 나누어 봅니다. 이 때, 나누었을 때 나머지가 0이 되는 경우가 생긴다면 소수가 아니므로 false를 return해줍니다. 나머지가 0이 되는 경우가 전혀 없이 for문을 빠져나오게 된다면 소수이겠죠?
   4. 여기 for문에서 1이 아닌 홀수로만 나누어보는 이유는(i=1, i+=2) 이미 여기 for문에 들어오게 될 n은 홀수이기 때문에, 짝수로 절대 나누어질 수 없습니다. 그래서 그 경우를 걸러준 것이에요.
   5. 또, for문에서 자신의 루트값보다 작거나 같은 수들로만 나누어보는 이유는(i*i<=n) n을 두 수의 곱으로 표현했을 때 두 수중 한 수는 무조건 루트n보다 작거나 같기 때문이에요
3. 전체적인 알고리즘 설명
   1. M부터 N까지 모든 숫자를 for문을 통해서 탐색해요. 이때, 가장 작은 소수(min)을 위해 큰 수부터 작은 수로 내림차순으로 수를 탐색해요.
   2. 각 수에 대해 is_prime함수를 통해 소수인지 판별하고, 만약 소수라면 min을 그 수로 덮어쓰고, sum에 그 수를 더해요, 또한 그 범위 내에 소수가 있다는 뜻이니 flag를 true로 바꿔요
   3. 모든 수에 대해 동작을 마치면 for문을 빠져나와요
   4. 범위내에 소수가 있다면, 즉 flag가 true이면 sum과 min을 차례로 출력해요
   5. 만일 범위내에 소수가 없다면, 즉 flag가 false이면 -1을 출력해요.
4. 끝!!!!

code

#include <iostream>
using namespace std;

bool is_prime(int n) {
	if ((n <= 1 || n % 2 == 0) && n != 2)
		return false;
	for (int i = 3; i * i <= n; i += 2) {
		if (n % i == 0)
			return false;
	}
	return true;
}
int main() {
	int M, N, min, sum = 0; // min : 가장 작은 소수 저장 / sum : 범위 내의 모든 소수의 합 저장
	bool flag = false; // 범위 내에 소수가 있는지 판별하는 bool 변수
	cin >> M >> N;
	for (int i = N; i >= M; i--) { // 큰 수부터 내림차순으로 수를 읽어와 min이 가장 작은 소수를 덮어쓸 수 있도록 함
		if (is_prime(i)) {
			min = i;
			sum += i;
			flag = true;
		}
	}
	if (flag) // 범위 내에 소수가 있는 경우
		cout << sum << '\n' << min << '\n';
	else // 범위 내에 소수가 없는 경우
		cout << -1 << '\n';
	return 0;
}