1929: 소수 구하기(에라토스테네스의 체)

• toc {:toc}

문제

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

입력

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

출력

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

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

에라토스테네스의 체

1. 배열을 생성한다. (+배열 초기화 코드에서는 false로 초기화)
2. 0과 1은 소수가 아니기 때문에 제외
3. 2는 소수이고 이후 2의 배수는 소수가 아니기 때문에 제외
4. 이와 같이 소수를 약수로 가지고 있는 수들을 제외
5. 소수를 선정하는 범위는 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;
}