[BOJ/C++] 1929. 소수 구하기

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

1929번: 소수 구하기

문제

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

입력

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

출력

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

풀이 방법

이번에는 이전에 포스팅했던 1978. 소수 찾기에서 썼던 Brute Force 방법을 이용하면 시간 초과가 날 것이다. N이 100만이기 때문이다.

 

필자는 제일 처음 시도했던 것은 O(N^(1/2)) 루트 알고리즘이다.

 

상당히 오래 걸리는 것을 확인했고, 그래서 에라토스테네스의 체 코드를 이용하기로 했다.

 

이론에 대한 설명은 이전 포스팅을 참고하면 된다.

https://minteul.tistory.com/309

[BOJ/C++] 1978. 소수 찾기

 

비교를 위해 루트 알고리즘과 에라토스테네스의 체를 이용한 결과를 모두 첨부하겠다.

 

// Code Plus BasicA
// 0x00. Math
// Written by Rylah
// Written Date : 2022.01.14
// https://minteul.tistory.com/310
// https://www.acmicpc.net/source/37539902

// 1929. 소수 구하기
// use Root Algorithm
// time Complexity : O(N^(1/2))

#include <bits/stdc++.h>
using namespace std;
bool isPrimeNumRootSolve(int n)
{
	if (n < 2)
		return false;
	else
	{
		for (int i = 2; i * i <= n; i++)
		{
			if (n % i == 0)
				return false;
		}
		return true;
	}

}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int a, b;
	cin >> a >> b;

	for (int i = a; i <= b; i++)
	{
		if (isPrimeNumRootSolve(i) == true)
			cout << i << '\n';
	}

	return 0;
}

 

// Code Plus BasicA
// 0x00. Math
// Written by Rylah
// Written Date : 2022.01.14
// https://minteul.tistory.com/310
// https://www.acmicpc.net/source/37540153

// 1929. 소수 구하기
// use Sieve of Eratosthenes
//time Complexity : O(NloglogN)

#include <bits/stdc++.h>
using namespace std;

int Eratos[1000003];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	for (int i = 2; i < 1000003; i++)
		Eratos[i] = i;

	for (int i = 2; i < 1000003; i++)
	{
		for (int j = i + i; j < 1000003; j += i)
		{
			if (Eratos[j] == 0)
				continue;
			Eratos[j] = 0;
		}
	}

	int a, b;
	cin >> a >> b;

	for (int i = a; i <= b; i++)
	{
		if (Eratos[i] != 0)
			cout << i << "\n";
	}

	return 0;
}