toc {:toc}

문제

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

입력

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

출력

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

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

에라토스테네스의 체

배열을 생성한다. (+ 배열 초기화 코드에서는 false 로 초기화)
0 과 1 은 소수가 아니기 때문에 제외
2 는 소수이고 이후 2 의 배수는 소수가 아니기 때문에 제외
이와 같이 소수를 약수로 가지고 있는 수들을 제외
소수를 선정하는 범위는 N 의 제곱근으로 한정

#include <iostream>
 
using namespace std;
 
int main() 
{
  	bool arr[1000001];
  	int M, N;
 
  	cin >> M >> N;
 
  	arr[0] = arr[1] = true;
 
  	for (int i=2; i*i<=N; i++)
  	{
    	if (!arr[i])
    	{
	      	for (int j = i * 2; j <= N; j += i)
    	    	arr[j] = true;
    	}
  	}
 
  	for (int i = M; i <= N; i++)
  	{
    	if (!arr[i])
     	 	cout << i << '\n';
  	}
	return 0;
}