[BOJ/C++] 소수(2581번)

1. 문제 개요

https://www.acmicpc.net/problem/2581

2581번: 소수

1-1. 설명

자연수 M과 N이 주어질 때 M이상 N 이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성한다. 

1-2. 제한사항

 - 입력의 첫째줄이 M, 둘째줄이 N 주어짐.

 - M과 N은 10,000이하의 자연수이며 M은 N보다 작거나 같음

 - 자연수 중 소수를 찾아 첫째줄에 합을, 둘째줄에 최솟값을 출력

 - M이상 N이하 자연수 중 소수가 없을 시 -1만 출력

 

---

 

2. 구현

2-1. 풀이

정말 단순하게 값 하나를 두고 2부터 나눠가며 나머지가 0이면 false, 모든 수가 나머지가 0이 아니면 true를 반환하게끔 하였다. 어차피 범위 내의 소수만 구하면 되는 부분이라 시간에 얽히지 않고 단순 코딩으로 진행하였다. 

2-2. 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool checkPrimeNumber(int num);

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

	for (int i = M; i <= N; i++) {
		if (true == checkPrimeNumber(i)) {
			if (firstNum == 0) {
				firstNum = i;
				sum++;
			}
			sum += i;
		}
	}
	cout << sum << endl;
	if (sum != -1) cout << firstNum << endl;
}

bool checkPrimeNumber(int num) {
	if (num < 2) return false;
	for (int i = 2; i * i <= num; i++) {
		if (num % i == 0) return false;
	}
	return true;
}