指定した範囲内で奇数個の約数を持つ要素の個数を求めるPythonプログラム

本記事では、以下の問題文に対する解決策について詳しく解説します。

問題文

問題 − ある範囲 [n, m] が与えられたとき、その範囲内に存在する「奇数個の約数を持つ数」の個数を求めます。

アプローチ

まず押さえておきたい重要な性質として、「完全平方数だけが奇数個の約数を持つ」ということが挙げられます。これは、約数が通常ペア（d と n/d）で現れるのに対し、完全平方数の場合は平方根に相当する約数だけがペアにならず単独で存在するためです。

したがって、この問題は「指定された範囲内に含まれる完全平方数の個数を数える」ことに帰着できます。

なお、n と m はどちらも範囲に含まれるため、境界値での誤差を避けるために、計算式では (n−1) の平方根を使用します。

それでは、実際の実装を見ていきましょう。

サンプルコード

# カウント用の関数
def count(n, m):
    return int(m**0.5) - int((n-1)**0.5)

# メイン処理
n = 25
m = 400
print("Number of odd squares are: ", count(n, m))

出力

Number of odd squares are: 16

この例では、25 から 400 の範囲内に 16 個の完全平方数（5² から 20² まで）が存在することが確認できます。

上記のコードでは、すべての変数と関数がグローバルスコープで宣言されています。計算量は O(1) であり、範囲が非常に大きい場合でも高速に動作する点がこの手法の大きな利点です。

まとめ

本記事では、指定された範囲内で奇数個の約数を持つ要素の個数を求める方法について学びました。「完全平方数のみが奇数個の約数を持つ」という数学的な性質を利用することで、ループ処理を使わずに平方根の計算だけで効率的に答えを導き出せることを確認しました。