指定された範囲内で奇数個の約数を持つ数の個数を求めるJavaプログラム

指定された範囲の中に、奇数個の約数（因数）を持つ数がいくつあるかを求めるJavaのコードを以下に示します。

サンプルコード

import java.io.*;
import java.util.*;
import java.lang.*;

public class Demo {
   public static int square_count(int low_range, int high_range) {
      return (int)Math.pow((double)high_range, 0.5) - (int)Math.pow((double)low_range - 1, 0.5);
   }

   public static void main(String[] args) {
      int low_range = 55, high_range = 1000;
      System.out.print("指定された範囲内で奇数個の約数を持つ数の個数 : " + square_count(low_range, high_range));
   }
}

実行結果

指定された範囲内で奇数個の約数を持つ数の個数 : 24

コードの解説

「Demo」という名前のクラスの中に、「square_count」というメソッドが定義されています。このメソッドは、範囲の下限と上限を表す2つの整数値を引数として受け取り、その範囲内で奇数個の約数を持つ数の個数を戻り値として返します。

ここで鍵となるのが、「ある整数が奇数個の約数を持つのは、その数が完全平方数であるとき、かつそのときに限る」という数学的な性質です。約数は通常「d と n/d」のペアで現れるため個数は偶数になりますが、完全平方数の場合は √n が自分自身と対になるため、約数の総数だけが奇数になります。

したがって、この問題は「指定された範囲内に含まれる完全平方数の個数を数える」問題に読み替えることができます。コードでは Math.pow を使って平方根を計算し、floor(√上限) − floor(√(下限−1)) という式で個数を求めています。(int) 型へのキャストによって小数点以下が切り捨てられるため、平方根の整数部分が正しく得られます。

main メソッドでは、下限値として 55、上限値として 1000 が定義され、それらを引数にして square_count メソッドが呼び出されます。√1000 の整数部分は 31、√54 の整数部分は 7 なので、31 − 7 ＝ 24 となり、その結果がコンソールに出力されます。実際、64（8²）から 961（31²）までの 24 個の完全平方数がこの範囲に含まれています。