알고리즘 문제풀이 [백준 1929]

🔎 BACKJOON 1929

• 문제

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

• 입력

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

• 출력

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

#include <iostream>
#include <cmath>

using namespace std;

int main(){
	int n, m, i, j;
	bool *prime;

	cin >> n >> m;
	prime = new bool[m + 1];
	fill_n(prime, m+1, 1);
	prime[0] = false;
	prime[1] = false;	

	for (i = 2; i <= sqrt(m); i++){
		if(prime[i] == true){
			for (j = i * 2; j <= m; j += i){
				prime[j] = false;
			}
		}
	}

	for (i = n; i <= m; i++){
		if(prime[i] == true){
			cout << i << "\n";
		}
	}

	return 0;
}

에라토스테네스의 체 문제풀이다. 간단하게 배열의 인덱스값과 구하고자하는 값이 동일할 경우 쉽게 응용가능하다.

문제 링크

풀이 깃허브 링크