[백준] 1929번: 소수 구하기

문제

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

입력

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

출력

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

예제 입력 1 복사

3 16

예제 출력 1 복사

3 5 7 11 13

 

#include<cmath>
#include<iostream>

int main()
{
	int M, N;
	std::cin >> M >> N;
	
	int* arr = new int[N+1];
	arr[1] = 0;
	for(int i = 2; i <= N; i++)
	{
		arr[i] = i;
	}
	
	for(int i = 2; i <= sqrt(N+1); i++)
	{
		if(arr[i] == 0)	continue;
		for(int j = i+i; j <= N; j+=i)
		{
			arr[j] = 0;
		}
	}
	
	for(int i = M; i <= N; i++)
	{
		if(arr[i] != 0)
		{
			printf("%d\n",arr[i]);			//std::endl을 사용할 시 시간 초과 발생!!!
		}
	}
	
	delete[] arr;
	return 0;
	
}

이번 문제는 이전과 달리 소수 구하는 최적의 알고리즘인 에라토스테네스의 채를 사용해야 합니다. 해당 알고리즘의 개념은 밑 사이트을 참고했습니다. 마지막에 배열을 출력할 때 std::endl을 사용할 시 시간 초과가 발생합니다. std::endl은 개행을 하는 동시에 내부 버퍼를 비워주는 역활도 하기 때문에 printf구문을 사용하거나 std::cout << '\n'을 사용하는게 좋겠습니다.