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

 

알고리즘 분류: 수학, 정수론, 소수 판정, 에라토스테네스의 체

문제 링크: https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

【 문제 】

 

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

 

 

 

【 입력 】

 

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

 

 

 

【 출력 】

 

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

 

 

 

【 풀이 】

 

소수(Prime Number)는 약수가 1과 자기 자신, 두 개뿐인 수를 의미한다.

그리고 범위가 주어졌을 때, 소수의 배수들을 모두 제외하여 소수의 개수를 구하는 알고리즘을

에라토스테네스의 체라고 한다.

예를 들어, M까지의 소수를 구하고자 한다면 2부터 M의 제곱근까지 검사해 보며 배열에서 소수의 배수들을 제거하는 방식인 것이다.

즉 단계적으로 설명하면 다음과 같다.

 

1. 2부터 차례대로 M까지 2의 배수들을 제거
2. 3은 소수이므로(자기 자신 제외) 1번처럼 M까지 3의 배수들을 제거
3. 4는 소수의 배수이므로 continue
4. 위 과정을 M의 제곱근까지 반복
5. 제거되지 않은 수들(소수) 출력

 

 

【 코드 】

 

#include<iostream>
#include<cmath>
using namespace std;

int arr[1000001];
int main(void)
{
	int n, m;
	cin >> n >> m;
	for (int i = 2; i <= m; i++)
		arr[i] = i;

	for (int i = 2; i <= sqrt(m); i++)		//	2부터 m의 제곱근까지
	{
		if (arr[i] == 0)		//	arr[i]가 0이면 이미 소수가 아닌 것
			continue;
		for (int j = i * i; j <= m; j += i)		//	i*i 전까지는 이미 검사가 되었기 때문에 i*i부터 시작
			arr[j] = 0;
	}

	for (int i = n; i <= m; i++)
	{
		if (arr[i] == 0)
			continue;
		else
			cout << arr[i] << '\n';
	}
	return 0;
}