[백준/C++] 1929번 : 소수 구하기 (sqrt, 에라토스테네스의 채 비교)

소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

---

특정 범위 안에 소수를 구하는 문제로, sqrt를 이용해 문제를 해결하는 방법과 에라토스테네스의 채를 이용해 해결하는 두 가지 방법으로 풀이해보았다.

✔️ sqrt 이용

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

bool IsPrime(int n)
{
	if (n <= 1) return false;

	for(int i = 2; i <= sqrt(n); i++)
	{
		if (n % i == 0)
			return false;
	}
	return true;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int M, N;
	cin >> M >> N;

	for(int i = M; i <= N; i++)
	{
		if (IsPrime(i))
			cout << i << '\n';
	}

	return 0;
}

✔️ 에라토스테네스의 채 이용

#include <iostream>
#include <string>
#include <cmath>
#include <vector>

using namespace std;


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int M, N;
	cin >> M >> N;

	vector<bool> check(N+1);
	check[0] = check[1] = true;
	for(int i = 2; i <= sqrt(N); i++)
	{
		if(!check[i])
		{
			for (int j = i + i; j <= N; j += i)
				check[j] = true;
		}
	}

	for(int i = M; i <= N; i++)
	{
		if (!check[i])
			cout << i << '\n';
	}

	return 0;
}

 

두 가지 풀이를 비교해본 결과, 에라토스테네스의 채를 이용하는 방법이 훨씬 적은 시간동안 문제를 해결할 수 있다는 점을 증명할 수 있었다.

 

---

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

1929번: 소수 구하기