計算機プログラミングI 第1回レポート

課題 (a) 素数の判定

ある数が素数かを判定するプログラムを作れ。

完全なプログラムは Prime.java である。この実行結果は Prime.txt である。

ある数が素数かを判定する問題は、

• ある数の最小の約数を見つける
• 最小の約数がある数と等しいかを調べる

これらをそれぞれをクラスメソッドleastDivisor, isPrimeとして定義した。後者は以下のようになる。

public static boolean isPrime(int x) {
  return (x==leastDivisor(x));
}

課題 (b) 計算時間

素数を判定するアルゴリズムの計算時間について考察せよ。

(a)のアルゴリズムでは、xが素数であることを判定するのにx回の繰り返しが必要である。……(略)

2つのアルゴリズムを比較すると、次の図のようになる:

課題 (c) (以下略)

感想・要望