C++で整数の完全平方約数をすべて数える方法

このチュートリアルでは、C++ を使って「ある整数の約数のうち、完全平方数であるもの(完全平方約数)」の個数を求めるプログラムを解説します。

ここでいう完全平方約数とは、与えられた数 n の約数の中で、1, 4, 9, 16 のようにある整数の 2 乗として表せる数のことを指します。

アプローチ

以下の手順で問題を解きます。

• i を 1 から √n まで順に調べ、n が i で割り切れるかどうかを確認します。
• n が i で割り切れる場合、i 自身が完全平方数であればカウントを 1 増やします。
• 同時に、ペアとなる約数 n / i も確認し、これが完全平方数であれば(i ≠ n/i の場合のみ)カウントを 1 増やします。

この方法により、O(√n) の計算量で効率的に答えを求めることができます。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
//完全平方数かどうかを判定する関数
bool if_psquare(int n){
   int sq = (int) sqrt(n);
   return (n == sq * sq);
}
//完全平方約数の個数を返す関数
int count_pdivisors(int n){
   int count = 0;
   for (int i=1; i*i <= n; ++i){
      if (n%i == 0){
         if (if_psquare(i))
            ++count;
         if (n/i != i && if_psquare(n/i))
            ++count;
      }
   }
   return count;
}
int main(){
   int n = 16;
   cout << "Total perfect divisors of " << n << " = " << count_pdivisors(n) << "\n";
   n = 12;
   cout << "Total perfect divisors of " << n << " = " << count_pdivisors(n);
   return 0;
}

出力

Total perfect divisors of 16 = 3
Total perfect divisors of 12 = 2

コードの解説

if_psquare 関数: 引数 n が完全平方数かどうかを判定します。sqrt(n) の小数点以下を切り捨てた整数値を 2 乗し、元の n と一致するかどうかを確認することで判定しています。

count_pdivisors 関数: 1 から √n までの各整数 i について、n が i で割り切れるかを調べます。割り切れる場合は、i と n / i の両方に対して完全平方数かどうかをチェックし、該当すればカウントを増やします。i == n / i となる場合(n が i の 2 乗の場合)は同じ約数を二重に数えないよう、条件式で除外している点がポイントです。

実行例の検証

例えば n = 16 の場合、約数は 1, 2, 4, 8, 16 であり、このうち完全平方数は 1(=1²)、4(=2²)、16(=4²)の 3 つです。一方、n = 12 の場合、約数は 1, 2, 3, 4, 6, 12 で、完全平方数は 1 と 4 の 2 つとなります。いずれもプログラムの出力と一致しています。