アルゴリズムを使って数学の問題を解く

アルゴリズムを使って数学の問題を解くことができます。アルゴリズムを使用することで、正確で信頼性の高い計算結果を得ることができます。

ここでは最大公約数を求めるユークリッドの互除法と素数を求めるエラトステネスの篩をご紹介します。

ユークリッドの互除法

問題：2つの正の整数aとbの最大公約数【Greatest Common Divisor:GCD】を見つけます。

※ユークリッド（Euclid）は、古代ギリシャの数学者であり、幾何学や数論などの分野で重要な貢献をした人物です。彼は紀元前300年頃に活動し、その業績は数学史上において大きな影響力を持っています。

この問題を解決するためには、ユークリッドの互除法と呼ばれるアルゴリズムが有効です。ユークリッドの互除法は、以下の手順で実行されます。

1. aをbで割り、余りrを取得します。
2. rが0でない場合、bをrにaをbに置き換え、1に戻ります。
3. rが0の場合、bが最大公約数です。

例えば、a=24, b=16の場合、以下のようになります。

1. 24を16で割ると、余りは8になります。
2. 8が0でないので、bを8にaを16に置き換え、1に戻ります。
3. 16を8で割ると、余りは0になります。したがって、最大公約数は8です。

＜サンプルプログラム＞

public class EuclidsAlgorithm {

    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    public static void main(String[] args) {
        int a = 24;
        int b = 16;
        int gcdResult = gcd(a, b);
        System.out.println("GCD of " + a + " and " + b + " is " + gcdResult);
    }
}

＜出力結果＞

練習問題1

以下の流れ図の読み方を講師から教わり、次の練習問題でJavaとして実装しなさい。

基本情報技術者試験　平成31年春期 午前問7

エラトステネスの篩

エラトステネスの篩は、素数を見つけるための古典的なアルゴリズムです。

※エラトステネスは、紀元前3世紀の数学者・地理学者であり、多岐にわたる分野で活躍しました。地中海にある2つの都市（アレクサンドリアとシラクサ）の間の距離を測定し、地球の円周を推定したという逸話を聞いたことのある方もいるでしょう。

素数とは、1と自分自身以外の正の約数を持たない自然数です。なお、1は素数ではありません。

このアルゴリズムは、以下の手順で実行されます。

1. 0からnまでのすべての自然数をリストアップする。
2. 0と１は素数ではないのでリストから削除する。
3. 最初の数2を素数とし、その倍数を素数リストから削除する。
4. 次に残った数の最初の数を素数とし、その倍数をリストから削除する。
5. 手順2と3を繰り返す。
6. リストに残った数は、素数です。

たとえば、nが30の場合、以下のようになります。

1. 0から30までの自然数をリストアップする。
2. 0と１は素数ではないのでリストから削除する。
3. 最初の数2を素数とし、その倍数をリストから削除する。
4. 残った数の最初の数3を素数とし、その倍数をリストから削除する。
5. 手順2と3を繰り返す。
6. リストに残った数は素数。

このように、エラトステネスの篩は、非常にシンプルなアルゴリズムであり、効率的に素数を見つけることができます。

※19行目でfor文の継続条件式が「 i * i < digits.length 」となっているのは、p * p より小さい倍数は既に他の素数の倍数としてふるい落とされているためです。例えば30までの素数であれば、7*7＝49で30を超えます。5より大きい素数の倍数は既にふるい落とされているので処理は不要なのです。

＜サンプルプログラム＞

import java.util.Scanner;

public class SieveOfEratosthenes {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.print("いくつまでの素数を知りたいですか？: ");
        int n = sc.nextInt();
        sc.close();

        boolean[] digits = new boolean[n + 1];//配列は0始まり

        for (int i = 0; i < digits.length; i++) {
            digits[i] = true;//配列はfalseで初期化されているため全てtrue(素数である)にする
        }

        digits[0] = digits[1] = false;//0と1は素数ではない

        for (int i = 2; i * i < digits.length; i++) {
            if (digits[i]) {
                for (int j = i * i; j < digits.length; j += i) {
                        digits[j] = false;
                }
            }
        }

        for (int i = 2; i < digits.length; i++) {
            if (digits[i]) {
                System.out.print(i + "  ");
            }
        }
    }
}

＜出力結果の例＞

投稿者プロフィール

山崎講師代表取締役

セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します！
この記事に間違い等ありましたらぜひお知らせください。

最新の投稿

• 新入社員2025年2月23日【新人エンジニア必読】「入りを量りて出を制す」の考え方を仕事に活かす
• 新人エンジニア研修講師2025年2月23日丁寧なのにイラッとする言葉
• 新入社員2025年2月23日【初心者の方も安心】Gitで避けたい主なトラブル10選
• 新入社員2025年2月23日【新人エンジニア向け】損失回避バイアスを知って開発リスクを減らそう