[C++] 소수 (제곱근을 활용하여 소수 판별) : 2581번

문제

 

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

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

---

문제 해석

 

이전 문제와 동일한 방법으로 소수를 판별하면 된다.

단 범위를 입력받으므로, 반복문의 범위를 입력받은 값으로 설정해주는 것과

소수들을 모두 더한 합, 그리고 최솟값을 추가로 출력해주면 된다.

 

+ 소수를 판별함에 있어서 2 ~ 자기자신 사이의 모든 수로 나누어보아도 되지만,

2 ~ 자기자신의 제곱근까지만 나누어보면 더 빠르게 판별할 수 있다.

 

12의 경우 2 x 6 / 3 x 4 / 4 x 3 / 6 x 2 의 쌍을 갖는데, 가운데를 기준으로 대칭을 이룬다.

12는 3.xx 의 제곱근을 가지며 이는 곧, 3.xx 까지만 판별하면 그 이후의 숫자부터는 대칭이기에

소수를 판별하는데 있어서 계산할 필요가 없다는 뜻이다.

 

C++ 에서 제곱근은 sqrt() 로 구할 수 있다. #include <cmath> 필요

 

---

풀이

#include <iostream>
#include <cmath>
using namespace std;
#define MAX 10000
int main()
{
	int min, max; // 범위 입력
	int sum = 0; // 소수의 합
	int primeMin = MAX; // 소수의 최솟값
	bool isPrime = true;

	cin >> min; cin.ignore();
	cin >> max;

	for (int i = min; i <= max; i++)
	{
		isPrime = true; // 소수라고 가정하고 시작
		if (i == 1) // 1 인 경우 예외 처리
		{
			isPrime = false;
			continue;
		}
		for (int j = 2; j <= sqrt(i); j++) // 제곱근 까지만
		{
			if (i % j == 0)
			{
				isPrime = false; // 소수가 아니면 브레이크
				break;
			}
		}
		if (isPrime) // 여전히 소수라면
		{
			sum += i; // 합하기
			if (i < primeMin)
			{
				primeMin = i;
			}
		}
	}
	if (sum == 0)
	{
		cout << -1;
	}
	else
	{
		cout << sum << "\n" << primeMin;
	}
}

 

마지막에 sum 이 여전히 0 이라는 뜻은

아무 소수도 더해지지 않았다는 뜻이므로, -1 을 출력하게 한다.