[Baekjoon] 2581번: 소수

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

2581번: 소수

 

---

 

문제 해결 과정

착안

어떤 하나의 수 \(n\)이 소수(prime number)인지 아닌지를 판별하기 위해서는 \(1, 2, ..., k (k ≤ \sqrt{n}\)을 만족하는 최대의 자연수\()\)로 모두 나누어서 확인할 수 있지만, 1 이상 \(n\) 이하의 자연수 중에서 소수인 것을 모두 찾는 과정에서 위와 같이 구하는 것은 계산적으로 유리하지 않다. 따라서, 에라토스테네스의 체(Sieve of Eratosthenes) 개념을 사용하여 구한다.

 

구현

에라모르겠다의 체에라토스테네스의 체를 구현하는 코드에서 살짝 응용하여 \(M ≤ i ≤ N\) 인 경우, \(i\)의 값을 합을 구하는 변수에 더하도록 하여 문제를 해결하였다. 참고로 에라토스테네스의 체를 이용해, \(1, 2, ..., n\)의 자연수 중 소수인 수들을 구하는 시간 복잡도는 \(O(n \log{(\log{n})})\) 이라고 한다('에라토스테네스의 체'의 시간 복잡도 증명 관련).

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>

using namespace std;

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

	vector<int> primes;
	vector<bool> sieve(N + 1);
	int sum_primes = 0;
	
	for (int i = 2; i <= N; i++)
	{
		if (!sieve[i])
		{
			sieve[i] = true;
			if (i >= M)
			{
				primes.push_back(i);
				sum_primes += i;
			}
		}
		
		for (int j = i; j <= N; j += i)
			sieve[j] = true;
	}

	if (!primes.empty())
		cout << sum_primes << endl << primes[0] << endl;
	else
		cout << "-1" << endl;
	
	return 0;
}

 

실행 결과

* 코드를 제출한 시점과 글 작성 시점이 달라, 주석 추가 등의 이유로 실행 결과의 코드 길이는 상이할 수 있음.