[백준알고리즘] 1929번: 소수 구하기 -C++

[백준알고리즘] 1929번: 소수 구하기 -C++

1929번: 소수 구하기 (acmicpc.net)

1929번: 소수 구하기

소수 구하기 문제다. 이전 1978 소수 찾기 문제와 2581 소수 문제와 유사하다.

각 문제별 풀이는 아래와 같다.

 

[백준알고리즘] 1978번: 소수 찾기 -Python, C++ (tistory.com)

[백준알고리즘] 1978번: 소수 찾기 -Python, C++

[백준알고리즘] 2581번: 소수 -C++ (tistory.com)

[백준알고리즘] 2581번: 소수 -C++

 

아무튼 여기서는 범위가 백만까지 간다. 그래서 보통은 여기서 에라토스테네스의 체를 사용하지 않는다.

에라토스테네스의 체의 경우에는 체를 채우기 위해서 시간 복잡도는 \(O(N log log N)\)이라고 한다. 아래는 그 설명인데 나중에 제대로 확인해야겠다.

stackoverflow.com/a/2582776

 

그래서 보통 여기서는 사람들이 제곱근을 이용한 소수 판정을 사용한다. N의 제곱근 이하만 N에 대한 약수가 있는 지를 확인하는 방법으로 시간 복잡도가 \(O(\sqrt{N})\)이 걸리게 된다.

 

그런데, 나는 혹시나 하고 에라토스테네스의 체를 사용했다 ㅎ;

당연히 소수를 찾을 때마다 cout을 이용해 출력하는 것은 시간초과가 발생했다.

근데 혹시나 출력 횟수를 줄이면 통과할까 궁금했다. 그래서 sstream 헤더에 포함된 ostringstream을 이용해 출력문을 해당 스트림 객체에 저장하고 있다가 한 번에 cout을 통해 출력을 해주었다. 그랬더니 시간 초과 해결 ^~^

 

아무튼 제곱근을 사용하지 않았는데 통과하는 게 신기해서 올려봤다.

 

#include <iostream>
#include <sstream>

bool field[1000001];

void eratosthenes(void);
void solve(void);

int main(void)
{
	eratosthenes();
	solve();
	return 0;
}

void eratosthenes(void)
{
	std::fill_n(field, 1000001, true);

	field[0] = field[1] = false;
	for (int i = 2; i < 500001; i++)
	{
		if (!field[i]) continue;

		int temp = 2;
		while (i * temp <= 1000000)
		{
			field[i * temp] = false;
			temp++;
		}
	}
}

void solve(void)
{
	int m, n;
	std::cin >> m >> n;

	std::ostringstream oss;
	for (int i = m; i <= n; i++)
		if (field[i]) oss << i << std::endl;

	std::cout << oss.str();
}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다