[C++] 백준 2581

백준의 2581번 문제 소수이다.

https://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이 된다.

 

 < 예제 >

 

이전의 1978번 문제와 유사하다.

이 문제는 숫자의 범위를 입력받고 그 안의 소수들의 합과 그 소수중 가장 적은 숫자를 찾는 문제이다.

 

#include <iostream>
using namespace std;

int main() {

	int low_num;
	int high_num;

	cin >> low_num;
	cin >> high_num;

	int count = 0, sum = 0, num = 0;
    
	for (int i = low_num; i <= high_num; i++) {
		for (int j = 2; j < i; j++) {
			if (i % j == 0) {
				count++;
			}
		}
		if (i != 1 && count == 0) {
			sum += i;
			if (num == 0) {
				num += i;
			}
		}
		count = 0;
	}

	if (sum == 0) {
		cout << -1;
	}
	else 
		cout << sum << '\n' << num << endl;

}

소수를 탐색하는 방법은 이렇다.

	for (int i = low_num; i <= high_num; i++) {
		for (int j = 2; j < i; j++) {
			if (i % j == 0) {
				count++;
			}
		}
		if (i != 1 && count == 0) {
			sum += i;
			if (num == 0) {
				num += i;
			}
		}
		count = 0;
	}

for문의 범위를 최저값 ~ 최고값으로 설정한 후 이중for문을 사용하여 2부터 해서 해당 숫자까지 차례로 나눈다.

i가 30이라면 2, 3, 4 ... 30으로 나누었을 때 나머지가 0인 값이 있을 경우 count가 증가하게 하였고

1은 소수가 아니기때문에 i가 1일 경우와 count가 0인 경우에 해당 숫자를 sum과 합치게 하였다.

 

초기에 num을 0으로 초기화 해두었고 가장 먼저 탐색되는 숫자를 num이 되도록 num+=i를 하였다.

그리고 마지막에 count를 0으로 다시 초기화해두어 다음 숫자도 탐색할 수 있게 하였다.

	if (sum == 0) {
		cout << -1;
	}
	else 
		cout << sum << '\n' << num << endl;

sum이 0이라면 소수가 존재하지 않는 것이기 때문에 -1을 출력하게 해주었고 그 외에는 

소수의 총 합과 가장 작은 소수를 출력하게 하였다.

 

1978번 문제와 유사하여 1978번 문제를 풀었다면 그리 어렵지 않게 풀 수 있는 문제이다.