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

문제

[C++] 백준 1929: 소수 구하기 SILVER 3
https://www.acmicpc.net/problem/1929

 

---

 

접근 방법

이 문제는 주어진 구간 [M, N] 안에 있는 모든 소수를 출력하는 문제다.
가장 전형적으로 떠올릴 수 있는 방법은 에라토스테네스의 체를 사용하는 것이다.

https://xeungcoding.tistory.com/58

소수(prime number) 구하기 - 에라토스테네스의 체

 

아이디어는 다음과 같다:

1) 먼저 0 ~ N까지 담을 수 있는 배열을 만든다.이렇게 하면 vect[i] == i 인 상태에서 시작한다.

• 이렇게 하면 vect[i] == i 인 상태에서 시작한다.

vector<int> vect(n + 1, 0);
for (int i = 0; i <= n; i++)
	vect[i] = i;

 

2) 2부터 N까지 순회하면서, 현재 수 i가 아직 지워지지 않았다면(vect[i] != 1) i의 배수들을 전부 지워주면 된다.

 

• vect[j] = 1로 만들어서 “이 인덱스는 소수가 아님”을 표시했다.
• 결국 마지막까지 1로 바뀌지 않은 수들만 소수로 남는다.

 

for (int i = 2; i <= n; i++)
{
	if (vect[i] != 1)
	{
		for (int j = i * 2; j <= n; j += i)
		{
			if (vect[j] != 1)
				vect[j] = 1;
		}
	}
}

 

3) 마지막으로, 구간 [M, N]을 순회하면서 vect[i] != 1 인 값들만 출력하면 된다.

for (int i = m; i <= n; i++)
{
    if (vect[i] != 1)
        cout << vect[i] << '\n';
}

 

이렇게 하면 소수를 매번 나눠보는 방식이 아니라,
한 번의 체 작업으로 전체 범위에 대한 소수 정보를 만들어두고 빠르게 출력할 수 있다.

 

구현 시 주의할 점

• 0과 1은 소수가 아니지만, 코드에서는
  • 0은 사용하지 않고
  • 1은 vect[1] = 1로 초기화되어 자동으로 “소수 아님” 상태라 추가 처리가 필요 없다.
• 배수를 지울 때 j = i * 2부터 시작해 j += i로 진행하면서
  vect[j] = 1로만 바꾸고, 이미 1인 경우는 다시 바꿀 필요가 없다.
• 이 코드는 i를 2부터 N까지 모두 돌고 있지만, 이론적으로는 sqrt(N)까지만 돌고 그 이후는 생략해도 된다.
  그래도 제한 내에서는 현재 구현으로도 충분히 통과한다.

 

 

---

 

코드

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int m = 0, n = 0;
	cin >> m >> n;

	vector<int> vect(n + 1, 0);
	for (int i = 0; i <= n; i++)
		vect[i] = i;

	for (int i = 2; i <= n; i++)
	{
		if (vect[i] != 1)
		{
			for (int j = i * 2; j <= n; j += i)
			{
				if (vect[j] != 1)
					vect[j] = 1;
			}
		}
	}
	for (int i = m; i <= n; i++)
	{
		if (vect[i] != 1)
			cout << vect[i] << '\n';
	}

	return 0;
}