[백준 1929]-소수구하기(C++)

문제

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

---

입력

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

---

출력

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

---

예제 입력 

3 16

예제 출력

3
5
7
11
13

 

💡이 문제는 에라토스테네스의 체를 활용하지 않으면 시간 초과가 나는 문제이다.

 

📕에라토스테네스의 체?

• 간단하게 설명하면 2의 배수를 지우고, 3의 배수를 지우고 ,,, 이렇게 각자의 배수들을 지우는 것이다.
• 이미 지워진 배수들은 넘어간다.
• 대신 지우는 범위가 굉장히 중요하다.
• 지우는 범위에 대한 설명은 아래 글로 대신한다.

1,2,3,5,6,10,15,30이 되겠지만 절반으로 나누었을때 √30이 정중앙에 올 것이다.
만약 √N보다 작은 범위에서 약수가 존재한다면 N은 소수가 아닐 것이다. 뒤에 √N보다 큰 범위는 조사할 필요가 없다. 약수는 딱 반으로 나눠서 있는지 없는지만 판단하면 되기 때문이다.

📗구현

1. 2부터 N까지의 배열을 만들어서 일단 모두 소수가 아니라고 가정을 한다.
   1. 초기화를 1 로함.
2. 2의 배수, 3의 배수, 5의 배수 ,,, √N의 배수까지 차례대로 지움.
   1. 지운다는 것은 초기화를 0으로 한다.
3. M부터 N까지의 범위에서 값이 1인 것[소수인 것]을 찾아서 출력한다.

 

코드

/*
M과 N사이의 소수를 찾아내자.
에라토스테네스의 체 이용
2의 배수 제거. 3의배수 제거. 어디까지
루트 N까지 제거
루트 N이 절반 나눳을때 마지막 약수 

*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int M, N;
int main()
{
	cin >> M >> N;
	vector<int>include(N + 1);
	for (int i = 2; i <= N; i++)
	{
		include[i] = 1;
	}
	include[1] = 0;
	for (int i = 2; i<=sqrt(N); i++) //2부터 루트 N까지 검사함.
	{
		if (include[i] == 0) //만약 이미 소수가 아니라고 판별낫다면 검사할필요없음,
		{
			continue;
		}
		for (int j = i*i; j<=N;j=j+i) //i의 배수부터 N까지 배수를 싹 다지움.
		{
			include[j] = 0;
		}
	}
	for (int i = M; i <= N; i++) //M부터 N까지의 소수를 출력하는데 소수는 include값이 1인것.
	{
		if (include[i] == 1)
		{
			cout << i<<"\n";
		}
	}
}

👀오류

나는 2부터 N까지만 1로 계산을 했는데 만약 M값이 1일 때를 생각을 안 해서 계속 오류가 났었다.

만약 오류가 난다면 1일 때의 경우의 수를 계산 안 해서 그럴 것이다.