[C++]백준 - 1929번 문제

1929번: 소수 구하기 (acmicpc.net)

1929번: 소수 구하기

 

1929번 : 소수 구하기

---

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

 

입력

---

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

 

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

에라토스테네스의 체를 사용하면 쉽게 풀립니다.

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

코드

---

#include <iostream>
using namespace std;

int main() 
{
	int M, N;
	
	cin >> M >> N;
	
	bool *er = new bool[N+1];
	fill_n(er, N + 1, false);
	for(int i = 2; i < N + 1; i++)
	{
	    if(!er[i])
	    {
	        if(M <= i) printf("%d\n", i);
	        for(int j = i; j < N + 1; j += i) 
	        {
	            er[j] = true;
	        }
	    }
	}
	delete[] er;
	return 0;
}

 

그 외

---