[BOJ] 2581 - 소수, 1929 - 소수 구하기

문제

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

M이상 N이하의 소수들의 합과 그 중 최솟값을 찾는 문제. 

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

M이상 N이하의 소수를 찾는 문제.

난이도

2581 - 난이도 下, 소요시간 10분

1929 - 난이도 上, 소요시간 4시간 이상..?

풀이 과정

사실 1929번은 예전에 풀다가 실행시간이 자꾸 초과되서 짜증나서 남겨놓았던 문제이다. 그래서 소요시간을 4시간 이상이라고 적어놨다.

두 문제는 사실상 동일한 문제지만 1929번에선 실행시간을 엄격하게 본다.

먼저 간단한 2581번부터 보자.

아이디어는 간단하다.

어떤 수가 소수인지를 판단하여 true/false를 return해주는 isPrime이라는 함수를 n에서 시작해서 1씩 줄여나가면서 m이 될 때까지 반복적으로 호출하여 true인 놈들만 sum에 더해주고 마지막에 나온 놈을 최솟값으로 결정하면 된다.

isPrime함수는 2~n-1까지의 수로 n을 나눠보고 나머지가 0이 되는 놈이 있으면 소수가 아니고 반복문이 끝날 때까지 나머지가 0이 되는 놈이 없으면 소수로 판단하면 된다.

즉, 다음과 같이 소스코드를 짜면 된다.

#include <iostream>
#include <vector>

using namespace std;

bool isPrime(int n)
{
	if (n == 1)
		return false;
	for (int j = 2; j < n; j++)
	{
		if (n % j == 0)
			return false;
	}
	return true;
}

int main(void)
{
	int m = 0, n = 0, min = 0, sum = 0;
	cin >> m; cin >> n;

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

매우 간단한 문제다.

그리고 이 isPrime 함수를 그대로 1929번에서 사용하면 실행시간 초과가 뜬다.

그래서 알고리즘을 변경해봤다.

요컨대, 소수가 아닌 수들은 반드시 어떤 소수의 배수이기 때문에 2~ n-1까지로 다 나누는 게 아니라, 소수들을 저장해놨다가 그 소수들로 나누어 떨어지는지만 보는 방식이다.

다음과 같이 코드를 짜봤다.

#include <iostream>
#include <vector>

using namespace std;

// n보다 작거나 같은 소수의 배열을 만드는 함수
vector<int> makePrime(int n)
{
	bool flag;
	vector<int> prime;
	prime.push_back(2);		// 최초에 2를 배열에 넣어줌
	for (int i = 3; i <= n; i++)
	{
		flag = true;
		for (int j = 0; j < prime.size() && j < i; j++)
		{
			if (i % prime[j] == 0)
				flag = false;	// i가 i보다 작은 소수들 중 하나로 나누어지면 소수가 아니므로
		}
		if(flag == true)
			prime.push_back(i);	// flag가 그대로 true면 소수이므로 배열에 추가
	}
	return prime;
}

int main(void)
{
	int n = 0, m = 0;
	cin >> n; cin >> m;
	vector<int> prime = makePrime(m);
	for (int i = 0; i < prime.size(); i++)
	{
		if(prime[i] >= n && prime[i] <= m)
			printf("%d\n", prime[i]);
	}
	return 0;
}

makePrime 함수를 호출하면 n보다 작거나 같은 소수들의 배열이 완성된다.

그런데, 이렇게해도 실행시간이 크게 줄어들지 않았다. 아마 위의 코드보다 다른 자잘한 계산들이 많아서 그런 것 같다.

계속 고민하고 다시짜고 해보다가

혹시 내가 모르는 소수 만드는 다른 알고리즘이 있는지 검색을 해보았더니...

이런게 나왔다. 에라토스테네스는 들어봤어도 에라토스테네스의 체는 처음 들어봤다.

2의 배수, 3의 배수, 5의 배수, ... 라는 '체'가 있다고 가정하고 그 체로 남아있는 숫자들을 걸러서 살아남은 놈이 소수라는 것이다.

음... 이거 언젠가 배웠을지도...?

아무튼 이 문제를 푸는 건 이 알고리즘을 알았다는 것 자체로 의미가 있다.

내가 몰랐던 부분은, n이 소수인지 판단하기 위해 n보다 작은 수들로 모두 나눠보는 것이 아니라, 제곱이 n보다 작거나 같은 수로만 나누면 된다는 것이었다. 불필요한 계산이 너무 많다는 것은 원래 알았지만 어느 범위까지 연산을 해야할지를 몰랐었다.

아무튼 이 사실을 알면 위의 소스코드들을 딱 한 줄씩만 고치면 된다.

isPrime 함수와 makePrime 함수만 바꿨고,

원래 있던 부분은 주석처리했다.

bool isPrime(int n)
{
	if (n == 1)
		return false;
	// for (int j = 2; j < n; j++)
	// ☆ 에라토스테네스의 체에 의하여 해당 소수의 제곱이 n보다 작거나 같을 때만 계산하면 됨
	for(int j = 2; j * j <= n; j++)
	{
		if (n % j == 0)
			return false;
	}
	return true;
}

vector<int> makePrime(int n)
{
	bool flag;
	vector<int> prime;
	prime.push_back(2);		// 최초에 2를 배열에 넣어줌
	for (int i = 3; i <= n; i++)
	{
		flag = true;
		// for (int j = 0; j < prime.size() && j < i; j++)
		// ☆ 에라토스테네스의 체에 의하여 해당 소수의 제곱이 i보다 작거나 같을 때만 계산하면 됨
		for (int j = 0; j < prime.size() && prime[j]*prime[j] <= i; j++)
		{
			if (i % prime[j] == 0)
				flag = false;	// i가 i보다 작은 소수들 중 하나로 나누어지면 소수가 아니므로
		}
		if(flag == true)
			prime.push_back(i);	// flag가 그대로 true면 소수이므로 배열에 추가
	}
	return prime;
}

시간 많이 들였는데 풀고 나니 허무하네