백준 1929 - 소수 구하기

문제 번호: 1929

문제 제목: 소수 구하기

문제 주소: https://www.acmicpc.net/problem/1929

문제 내용

M이상 N이하인 소수를 모두 출력한다.

테스트 케이스

1 5	2 3 5
3 16	3 5 7 11 13
999900 1000000	999907 999917 999931 999953 999959 999961 999979 999983

문제 풀이

에라토스테네스의 체를 이용해 풀어야 하는 문제다.
짝수는 2의 배수로 제거하고, 나머지 홀수는 해당 수의 배수로 제거한다.
이미 제거된 인덱스에 작업이 중복되어 일어날 수 있기 때문에 이에 대한 예외처리를 진행해줄 필요가 있다.
출력이 최대 78498회까지 일어나므로 개행을 출력할 때 endl로 하지 말고 "\n"으로 해야 한다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_1929()
{
	// 소수는 false, 합성수는 true
	bool primeArr[1000001] = { false };
	for (int j = 4; j <= 1000000; j += 2)
	{
		primeArr[j] = true;
	}
	for (int i = 3; i <= 1000000; i += 2)
	{
		for (int j = i * 2; j <= 1000000; j += i)
		{
			if (!primeArr[i])
			{
				primeArr[j] = true;
			}
		}
	}
	
	int M;
	int N;
	cin >> M >> N;
	M = M < 2 ? 2 : M;
	for (int i = M; i <= N; i++)
	{
		if (!primeArr[i])
		{
			cout << i << "\n";
		}
	}
	return;
}