[백준/BOJ] 2581번: 소수 - C++ 문제 풀이

문제 설명

 

 

문제 링크: http://www.acmicpc.net/problem/2581

2581번: 소수

 

 

풀이

정의를 보면 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다.

 

이 정의에 따라 소수를 구하는 함수를 만들고, 메인 함수에서 M부터 N까지 루프를 거치면서 소수면 총합에 더하고, 현재 가장 작은 소수보다 더 작으면 최소 소수를 갱신하면 되는 문제이다.

 

그런데 작은 수부터 소수 검사를 하면 최소 소수를 찾기 위해 비교하는 코드가 필요하므로 큰 수부터 검사하는 게 좋겠다.

int main() {
	int M, N;
	cin >> M >> N;
    
	int sum = 0;
	int min = -1;
	for(int i = N; i >= M; i--){		
		if ( isPrime(i)){	// 소수인가?
			sum += i;
			min = i;
		}
	}
	
	if ( min == -1){
		cout << min << "\n";
	}
	else{
		cout << sum << "\n" << min << "\n";
	}
	return 0;
}

 

소수인지 판단하는 함수는 다음과 같다

bool isPrime( int p){
	for(int i = 2; i < p; i++){
		if (p % i == 0){
			return false;
		}
	}
	return true;
}

 

그런데, 테스트 입력도 검사한 후 위의 코드를 백준에 제출하니 "틀렸습니다"라고 나와서 좀 당황했다.

어디가 잘못된 걸까?

 

문제를 다시 읽어보니 자연수 M, N을 입력받아 소수를 찾는다라고만 되어있지, 소수의 정의인 1보다 큰 자연수 중에서 찾는다라는 것은 어디에도 없는 나 스스로 만든 가정이라는 알게 되었다. (위 함수에 1을 대입하면 소수가 아닌데도 true를 리턴한다.)

글을 읽으시는 분들도 이런 문제로 당황하는 일이 생기지 않았으면 좋겠네요.

 

그래서 메인 함수에서 입력받은 M이 1일 경우 2로 만들어서 isPrime 함수 호출 시 입력값이 2보다 작을 수는 없도록 만들어서 문제를 해결했다. (실제 사용하는 코드가 2보다 작은 경우가 생길 가능성이 있다면 검사하는 코드가 있는 게 좋겠다. 적어도 assert 디버그 코드는 있어야 할 것이다.)

 

이제 코드는 작동한다.

하지만 좀 더 개선한 방법은 없을까?

isPrime 함수는 2부터 입력값 p-1까지 루프를 돌면서 약수가 있는지 검사한다.

만약 p가 상당히 큰 자연수라면 위 코드를 수행하는 시간이 비약적으로 늘어나게 될 것이다.

 

우리는 약간의 수학적 지식을 사용하면 검사 시간을 꽤 줄일 수 있다.

2부터 입력값 p-1까지 검사하는 대신에 sqrt(p) 까지만 검사해도 충분하다는 것이 증명되어 있기 때문이다.

2부터 sqrt(p) 값까지 검사해서 약수가 없다면 p는 소수라고 확정할 수 있다.

 

개선된 코드는 다음과 같다.

bool isPrime( int p){	
	// p는 2 이상의 자연수를 가정한다.
	//if ( p == 1) return false;

	// sqrt(p) 값까지는 검사한다.
	int sqrtP = (int)sqrt(p) + 1;

	for(int i = 2; i < sqrtP; i++){
		if (p % i == 0){
			return false;
		}
	}	
	return true;
}

 

 

 

소스 코드

#include <iostream>
#include <math.h>
using namespace std;

bool isPrime( int p){
	
	// p는 2 이상의 자연수를 가정한다.
	// if ( p == 1) return false;

	// sqrt(p) 값까지는 검사한다.
	int sqrtP = (int)sqrt(p) + 1;

	for(int i = 2; i < sqrtP; i++){
		if (p % i == 0){
			return false;
		}
	}	
	return true;
}

int main() {
	int M, N;
	cin >> M >> N;

	if (M==1) M++;	// M이 1이 되는 것을 막아준다

	int sum = 0;
	int min = -1;
	for(int i = N; i >= M; i--){
		
		if ( isPrime(i)){
			sum += i;
			min = i;
		}
	}
	
	if ( min == -1){
		cout << min << endl;
	}
	else{
		cout << sum << endl << min << endl;
	}
	return 0;
}