[백준 2061] 좋은 암호 (C#, C++) - soo:bak

문제 링크

2061번 - 좋은 암호

설명

암호 키 K는 큰 수 문자열(최대 100자리)이다. L 미만의 소수로 나누어떨어지면 좋은 암호가 아니므로 가장 작은 약수와 함께 BAD r을 출력한다. 어떤 소수로도 나누어떨어지지 않으면 GOOD이다.

접근법

L 미만 소수를 에라토스테네스로 구한다. 각 소수 p에 대해 문자열 K를 자릿수 순회하며 나머지 rem = (rem*10 + digit) % p를 계산한다. 나머지가 0이면 즉시 BAD p를 출력하고 종료한다. 끝까지 없으면 GOOD. 범위상 int로 충분하다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var parts = Console.ReadLine()!.Split();
    string K = parts[0];
    int L = int.Parse(parts[1]);

    bool[] comp = new bool[L];
    for (int i = 2; i * i < L; i++) {
      if (comp[i]) continue;
      for (int j = i * i; j < L; j += i) comp[j] = true;
    }

    for (int p = 2; p < L; p++) {
      if (comp[p]) continue;
      int rem = 0;
      foreach (char c in K)
        rem = (rem * 10 + (c - '0')) % p;
      if (rem == 0) {
        Console.WriteLine($"BAD {p}");
        return;
      }
    }

    Console.WriteLine("GOOD");
  }
}

C++

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

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

  string K; int L;
  if (!(cin >> K >> L)) return 0;

  vector<bool> comp(L, false);
  for (int i = 2; i * i < L; i++) if (!comp[i])
    for (int j = i * i; j < L; j += i) comp[j] = true;

  for (int p = 2; p < L; p++) {
    if (comp[p]) continue;
    int rem = 0;
    for (char c : K) rem = (rem * 10 + (c - '0')) % p;
    if (rem == 0) {
      cout << "BAD " << p << '\n';
      return 0;
    }
  }

  cout << "GOOD\n";
  return 0;
}