[C/C++] 백준 2581번 - 소수 (에라토스테네스의 체)

 

 

 

<코드>

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

int check[10001]; // 0: 초기상태, 1: 소수, 2: 소수X

int main()
{
	int N, M;
	int ans = 0;
	int mini = 10000;

	for (int i = 2; i <= 10000; i++)
	{
		if (check[i] == 2) continue;
		else check[i] = 1;
		for (int j = i + i; j <= 10000; j += i)
		{
			check[j] = 2;
		}
	}

	cin >> N >> M;

	for (int i = N; i <= M; i++)
	{
		if (check[i] == 1) {
			mini = min(mini, i);
			ans += i;
		}
	}
	
	if (ans == 0) {
		cout << -1;
	}
	else {
		cout << ans << '\n';
		cout << mini << '\n';
	}
	
}

 

풀이 방법

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 알고리즘으로 위와같이 소수를 빠르게 구할 수 있다.

 

 

 

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

2581번: 소수