728x90
[백준알고리즘] 1929번: 소수 구하기 -C++
소수 구하기 문제다. 이전 1978 소수 찾기 문제와 2581 소수 문제와 유사하다.
각 문제별 풀이는 아래와 같다.
[백준알고리즘] 1978번: 소수 찾기 -Python, C++ (tistory.com)
[백준알고리즘] 2581번: 소수 -C++ (tistory.com)
아무튼 여기서는 범위가 백만까지 간다. 그래서 보통은 여기서 에라토스테네스의 체를 사용하지 않는다.
에라토스테네스의 체의 경우에는 체를 채우기 위해서 시간 복잡도는 \(O(N log log N)\)이라고 한다. 아래는 그 설명인데 나중에 제대로 확인해야겠다.
그래서 보통 여기서는 사람들이 제곱근을 이용한 소수 판정을 사용한다. 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();
}
잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다
728x90
'algorithm > 백준알고리즘' 카테고리의 다른 글
[백준알고리즘] 9020번: 골드바흐의 추측 -C++ (0) | 2021.01.18 |
---|---|
[백준알고리즘] 4948번: 베르트랑 공준 -C++ (0) | 2021.01.18 |
[백준알고리즘] 2581번: 소수 -C++ (0) | 2021.01.17 |
[백준알고리즘] 2775번: 부녀회장이 될테야 -C++ (0) | 2021.01.17 |
[백준알고리즘] 1193번: 분수찾기 -C++ (0) | 2021.01.17 |