[백준 8658] Liczba (C#, C++) - soo:bak

문제 링크

8658번 - Liczba

설명

정수 n이 주어질 때, 1부터 n 사이에서 n의 약수가 아닌 가장 작은 수와 가장 큰 수를 출력하는 문제입니다.

1과 n은 항상 약수이므로 답은 2부터 n-1 사이에서 찾습니다.

접근법

먼저, 최소 비약수를 찾습니다. 2부터 시작해서 n으로 나누어떨어지지 않는 첫 번째 수를 찾습니다.

다음으로, 최대 비약수를 찾습니다. n-1부터 시작해서 n으로 나누어떨어지지 않는 첫 번째 수를 찾습니다.

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = long.Parse(Console.ReadLine()!);

      var minNon = 2L;
      while (n % minNon == 0)
        minNon++;

      var maxNon = n - 1;
      while (n % maxNon == 0)
        maxNon--;

      Console.WriteLine($"{minNon} {maxNon}");
    }
  }
}

C++

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

typedef long long ll;

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

  ll n; cin >> n;

  ll minNon = 2;
  while (n % minNon == 0)
    minNon++;

  ll maxNon = n - 1;
  while (n % maxNon == 0)
    maxNon--;

  cout << minNon << " " << maxNon << "\n";

  return 0;
}