Baekjoon 1929 소수 구하기

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

소스결과 2884 KB / 16 ms

출처 Baekjoon

언어 C++ 17

분류 에라토스테네스의 체

 

설명

입력된 범위 내에 있는 소수를 전부 출력하자

 

최대 범위가 100만이다. 시작 값이 소수인지를 확인하면 절대 시간내에 해결이 안된다.

에라토스테네스의 체를 이용해 100만까지 구한 후 소수를 따로 저장하면 된다.

 

알고리즘

1. 에라토스테네스의 체를 이용해 소수만 저장한다.

2. 저장된 소수를 처음부터 탐색한다.

3. 범위 내에 들어가면 출력하고 범위를 벗어나면 출력을 종료한다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 1000000;

void eratos(bool arr[MAX + 1]) {

	arr[0] = arr[1] = true;
	for (int i = 2; i < MAX / 2 + 1; i++)
	{
		if (!arr[i])
		{
			for (int j = i * 2; j <= MAX; j += i)
				arr[j] = true;
		}
	}
}

int main()
{
	bool prime[MAX + 1] = {};

	eratos(prime);

	int to, des; cin >> to >> des;

	for (int i = to; i <= des; i++)
		if (!prime[i])
			cout << i << '\n';

	return 0;
}