[백준 1816] 암호 키 (C#, C++) - soo:bak

문제 링크

1816번 - 암호 키

설명

주어진 수 S의 모든 소인수가 10^6보다 크면 암호 키로 적절(YES), 10^6 이하 소인수가 하나라도 있으면 부적절(NO)입니다. S는 최대 10^18이므로 직접 소인수분해 대신 소수 나눗셈만으로 판정합니다.

접근법

먼저 에라토스테네스의 체로 백만 이하의 소수를 모두 구합니다.

각 S에 대해 이 소수들로 나누어떨어지는지 확인합니다. 하나라도 나누어떨어지면 백만 이하의 소인수가 있으므로 NO를 출력하고, 끝까지 나누어떨어지지 않으면 YES를 출력합니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    const int LIMIT = 1_000_000;
    var isComp = new bool[LIMIT + 1];
    var primes = new List<int>();
    for (var i = 2; i <= LIMIT; i++) {
      if (isComp[i]) continue;
      primes.Add(i);
      for (var j = i * 2; j <= LIMIT; j += i)
        isComp[j] = true;
    }

    var n = int.Parse(Console.ReadLine()!);
    for (var t = 0; t < n; t++) {
      var s = long.Parse(Console.ReadLine()!);
      var ok = true;
      foreach (var p in primes) {
        if (s % p == 0) { ok = false; break; }
      }
      Console.WriteLine(ok ? "YES" : "NO");
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;

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

  const int LIMIT = 1'000'000;
  vb isComp(LIMIT + 1, false);
  vi primes;
  for (int i = 2; i <= LIMIT; i++) {
    if (isComp[i]) continue;
    primes.push_back(i);
    for (int j = i * 2; j <= LIMIT; j += i)
      isComp[j] = true;
  }

  int n; cin >> n;
  while (n--) {
    ll s; cin >> s;
    bool ok = true;
    for (int p : primes) {
      if (s % p == 0) { ok = false; break; }
    }
    cout << (ok ? "YES" : "NO") << "\n";
  }

  return 0;
}