(C++) 백준 1816번 - 암호 키

https://www.acmicpc.net/problem/1834

문제

> 실제에서 암호는 매우매우 큰 소수로 이루어진다. 하지만 문제에선 "매우매우 큰"을 10^6으로 정의한다.
> S가 주어질때 모든 수인수가 10^6보다 크면 적절한 암호 키이고, 작다면 적절하지 못한 암호 키이다.
> 적절한 암호키인지 판단해라.

접근

에라토스테네스의 체를 이용해 소수를 미리 구해둔다.
입력받은 수를 해당 소수들로 쭉 나눴을때 하나라도 나눠지면 NO, 아니라면 YES를 출력한다.
10^6보다 작은 소수를 포함하지 않는 수 라는 뜻이기 때문이다.

문제해결

> 2부터 10^6까지 bool을 이용해 2부터 각각의 배수를 제외하며 반복해 값을 넣는다. 각각의 배수는 인수로 해당 값을 갖는다는 뜻이기 때문이다.
> 위 과정을 통해 소수만 남겨져 에라토스테네스의 체가 만들어진다.
> 생성한 메소드를 이용해 입력받은 수를 체에 들어있는 소수로 나눈다.
> 나뉜다면 10^6보다 작은 소인수를 가졌으므로 NO 아니라면 YES를 출력한다.

코드

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

vector<bool> is_prime(1000001, true);
vector<long long> prime;
void sieve()
{
	for (int i = 2; i < 1000001; i++)
	{
		if (is_prime[i] == true)
		{
			prime.push_back(i);
			for (long long j = 1LL * i * i; j < 1000001; j += i)
			{
				is_prime[j] = false;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	cin >> N;

	sieve();

	while (N--)
	{
		long long S;
		cin >> S;
		bool result = true;

		for (long long l : prime)
		{
			if (S % l == 0)
			{
				result = false;
				break;
			}
		}
		cout << (result ? "YES" : "NO") << '\n';
	}
}

후기

처음 문제를 마주했을때 아무런 해결법도 생각나지않았다.
에라토스테네스의 체라는걸 만들어서 해결하라는 문제라는걸 알았고 이를 통해 소수들만 검증하여 뽑아내는 알고리즘을 새로 알게 되었다.
최근 푼 문제중 가장 어려웠다.