ユークリッド互除法を使わずに最大公約数を求めたい

Question

###実現したいこと
三つ以上の整数の最大公約数を求める。
###問題点

最大公約数が違う答えになる。
./kadai09 40 45 50
"最大公約数は0"

###追記5/21
私なりにいただいた助言をもとに考えなおしてみました。でもうまくいかないです。

やりたいこととしては、まずargc[1]とargc[2]の最大公約数を求めて、その答えとargc[3]の最大公約数を求めるというのをどんどん繰り返していく、、、というかんじです。

###コード

#include<iostream>
#include<cstdlib>
int main(int argc,char* argv[])
{
    int maxk=0;
    int ans=0;
    int i,j,k;
    for(i=1;i<argc;i++){
        for(j=std::atoi(argv[i]);j>0;j--){
        if(std::atoi(argv[i])%j==0){
            if(std::atoi(argv[i+1])%j==0){
                ans=j;
                break;
            }
        }
        for(k=ans;k>0;k--){
            if(ans%k==0){
                if(std::atoi(argv[i+2])%k==0){
                    maxk=k;
                    break;
                }
            }
        }
    }
    }
    std::cout<<"最大公約数は"<<maxk<<"\n";
    return 0;
}

Comments

[Yasumichi]

argv[0] には、実行ファイル名が入るのは理解していますか？また、argc には、実行ファイル名も含めた引数の数が入ります。

[Yasumichi]

入力例も提示してください。最初の引数に数の個数を入れる想定でしょうか？

[Yasumichi]

スルーされてるかもしれませんが。
一度、計算のイメージを数式だけで書いてみた方が良さそうです。今のループだと存在しない argv[i] を読み込んでいます。

[Yasumichi]

共通な数で割れるだけ割っていく方法をやりたいということですね。

Answer 1

まず自分の書いたコードがどういう動きをするのか確かめてください。

./kadai09 40 45 50 で起動したということは、

• argc = 4
• argv[0] = "./kadai09"
• argv[1] = "40"
• argv[2] = "45"
• argv[3] = "50"
• argv[4] = NULL

となっています。

for文の i = std::atoi(argv[1]) で、i は 40 になります。
i > 0 だから、中に入ります。
if文の std::atoi(argv[i]) ですが、argv[40] なんか参照してはいけません。

for文で、i が 40 から 1 まで変化します。これが最大公約数の候補です。
argv[1]、argv[2]、argv[3] の全部を割り切れるものを見つけるわけだから、argv[j]
として j を 1 から 3 まで変えて i で割って余りがあるかどうかを見ればよいのです。

#include <iostream>
#include <cstdlib>

int main(int argc, char* argv[])
{
    int maxk = 0;
    int i, j;
    for (i = std::atoi(argv[1]); i > 0; i--) {
        for (j = 1; j < argc; j++) {
            if (std::atoi(argv[j]) % i != 0) break;
        }
        if (j == argc) {
            maxk = i;
            break;
        }
    }
    std::cout << "最大公約数は " << maxk << "\n";
    return 0;
}

非常に効率の悪いコードですが、とりあえず正しく動くはずです。

この回答についてのコメントをお願いします。

Comments

[langhtorn]

iが盲点でした。アドバイスありがとうございました。

Answer 2

あまり美しくないし、例外処理もしていませんが、以下のようなコードでいかがでしょうか？

#include<iostream>
#include<cstdlib>
using namespace std;

int main(int argc,char* argv[])
{
    int maxk=0; // 最大公約数
    int i;
    int j;

    // プログラムを除き２つ以上の引数が与えられなかった場合
    if (argc < 3) {
        cout << "2つ以上の整数を入力してください。" << endl;
        return	-1;
    }

    // 以下、例外処理は省略

    // 引数の最小値を求めつつ、配列に格納
    int size = argc - 1;    // コマンド以外の引数の数
    int *num = new int[size];
    num[0] = atoi(argv[1]);
    int min = num[0];
    for(i=1;i<size; i++) {
        num[i] = atoi(argv[i+1]);
        if (min > num[i]) {
            min = num[i];
        }
    }

    // 共通な数で割れるだけ割っていく
    for(i=min; i>0; i--) {
        bool flg = true;    // すべて割り切れるか否か
        for(j=0; j<size; j++) {
            if (num[j] % i != 0) {
                // 割り切れなかったので false にしてループを抜ける
                flg = false;
                break;
            }
        }
        // この時点で flg が true ならばすべて割り切れたということ
        if (flg == true) {
            maxk = i;
            break;
        }
    }

    // 結果の表示
    cout<<"最大公約数は"<<maxk<<"\n";
    return 0;
}

ちょっと問題とずらしてますし、using namespace std; とか使っているのであれですが。

Answer 3

参考情報

• 【競プロ】3個以上の整数の最大公約数と最小公倍数

https://math.nakaken88.com/textbook/cp-gcd-and-lcm-of-many-integers/