[백준 13225] Divisors (C#, C++) - soo:bak

문제 링크

13225번 - Divisors

설명

여러 정수의 약수 개수를 구하는 상황에서, 테스트케이스의 수 C (최대 10)와 각 테스트케이스마다 정수 n (1 ≤ n < 10,000)이 주어질 때, 각 n의 약수 개수를 n과 함께 출력하는 문제입니다.

약수는 1부터 n까지의 정수 중 n을 나누어떨어지게 하는 수를 의미합니다.

접근법

1부터 n까지 모두 확인하는 대신, 제곱근까지만 확인하는 최적화를 사용합니다.

1부터 √n까지 반복하며 n을 나누어떨어지게 하는 약수 d를 찾으면, d와 n/d 두 개의 약수가 존재합니다. 단, d = √n인 경우(완전제곱수)는 d와 n/d가 같으므로 하나만 세어야 합니다.

이 방법으로 시간 복잡도를 O(√n)으로 줄일 수 있습니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var t = int.Parse(Console.ReadLine()!);
      
      for (var i = 0; i < t; i++) {
        var num = int.Parse(Console.ReadLine()!);
        var cnt = 0;
        
        for (var divisor = 1; divisor * divisor <= num; divisor++) {
          if (num % divisor == 0)
            cnt += (divisor * divisor == num) ? 1 : 2;
        }
        
        Console.WriteLine($"{num} {cnt}");
      }
    }
  }
}

C++

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

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

  int t; cin >> t;
  
  for (int i = 0; i < t; i++) {
    int num; cin >> num;
    int cnt = 0;
    
    for (int divisor = 1; divisor * divisor <= num; divisor++) {
      if (num % divisor == 0)
        cnt += (divisor * divisor == num) ? 1 : 2;
    }
    
    cout << num << " " << cnt << "\n";
  }
  
  return 0;
}