(C++) - 백준(BOJ) 1816 : 암호 키

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

1816번: 암호 키

에라토스테네스의 체를 이용하는 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

소수의 개수 n, 에라토스테네스의 체를 이용하기 위한 일차원 배열 ck, 소수들을 저장할 변수 prime을 선언한 뒤 입력받습니다.

📔 풀이과정

자연수 n이 √n 이하의 어떤 소수로도 나누어 떨어지지 않으면 n 은 소수임이 보장됩니다.따라서 입력받는 수가 100만 이하의 소수로 나누어 떨어지지만 않으면 n은 소수가 됩니다. 따라서 100만이하의 소수를 구해 prime에 저장한 후 매 숫자마다 나누어 떨어지는지 여부만 검사해 답을 출력합니다.

📔 정답출력

숫자가 prime에 있는 원소로 나누었을 때 나누어 떨어지지 않는다면 YES를, 아니라면 NO를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, ck[1000001];
vector <int> prime;

void makePrime(){
  for(ll i = 2; i <= 1000000; i++){
    if(ck[i]) continue;
    for(ll j = i + i; j <= i; j += i){
      ck[j] = 1;
    }
  }
  for(ll i = 2; i <= 1000000; i++){
    if(!ck[i]) prime.push_back(i);
  }
}

bool isValid(ll num){
  for(auto p : prime){
    if(num % p == 0) return false;
  }
  return true;
}

int main(){
  cin >> n;
  makePrime();
  for(ll i = 0, num; i < n; i++) {
    cin >> num;
    if(isValid(num)) cout << "YES\n";
    else cout << "NO\n";
  }
}