[백준 1837] 암호제작 (C#, C++) - soo:bak

문제 링크

1837번 - 암호제작

설명

두 소수의 곱으로 이루어진 암호가 안전한지 판별하는 문제입니다.

접근법

먼저 k 미만의 소수를 에라토스테네스의 체로 구합니다.

각 소수에 대해 문자열 p를 자릿수 순회하며 나머지를 계산합니다.

어떤 소수로든 나누어떨어지면 BAD와 해당 소수를 출력하고, 끝까지 없으면 GOOD을 출력합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var line = Console.ReadLine()!.Split();
    var num = line[0];
    var k = int.Parse(line[1]);

    var isComposite = new bool[k];
    for (var i = 2; i * i < k; i++) {
      if (isComposite[i]) continue;
      for (var j = i * i; j < k; j += i)
        isComposite[j] = true;
    }

    foreach (var p in PrimesUpTo(k, isComposite)) {
      var rem = 0;
      for (var i = 0; i < num.Length; i++)
        rem = (rem * 10 + (num[i] - '0')) % p;
      if (rem == 0) {
        Console.WriteLine($"BAD {p}");
        return;
      }
    }
    Console.WriteLine("GOOD");
  }

  static System.Collections.Generic.IEnumerable<int> PrimesUpTo(int k, bool[] isComposite) {
    for (var i = 2; i < k; i++)
      if (!isComposite[i]) yield return i;
  }
}

C++

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

typedef vector<bool> vb;

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

  string num; int k;
  if (!(cin >> num >> k)) return 0;

  vb comp(k, false);
  for (int i = 2; i * i < k; i++)
    if (!comp[i])
      for (int j = i * i; j < k; j += i)
        comp[j] = true;

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

  return 0;
}