백준 1816번 암호 키

문제 링크입니다: https://www.acmicpc.net/problem/1816

1816번: 암호 키

에라토스테네스의 체를 이용하여 소수를 구하고

S가 그 소수들에 의하여 나누어 떨어지지 않는지를 판별하는 문제였습니다.

 

	#include <iostream>
	#include <vector>
	using namespace std;
	const int MAX = 1e6 + 1;
	int minFactor[MAX];
	vector<int> prime;
	void eratosthenes(void)
	{
	minFactor[0] = minFactor[1] = -1;
	for (int i = 2; i < MAX; i++)
	{
	minFactor[i] = i;
	}
	for (int i = 2; i*i < MAX; i++)
	{
	if (minFactor[i] == i)
	{
	for (int j = i * i; j < MAX; j += i)
	{
	if (minFactor[j] == j)
	{
	minFactor[j] = i;
	}
	}
	}
	}
	for (int i = 2; i < MAX; i++)
	{
	if (minFactor[i] == i)
	{
	prime.push_back(i);
	}
	}
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;
	eratosthenes();
	for (int n = 0; n < N; n++)
	{
	long long S;
	cin >> S;
	bool flag = true;
	for (int i = 0; i < prime.size(); i++)
	{
	if (S%prime[i] == 0)
	{
	flag = false;
	break;
	}
	}
	if (flag)
	{
	cout << "YES\n";
	}
	else
	{
	cout << "NO\n";
	}
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~