としおの読書生活

田舎に住む社会人の読書記録を綴ります。 主に小説や新書の内容紹介と感想を書きます。 読書の他にもワイン、紅茶、パソコン関係などの趣味を詰め込んだブログにしたいです。

2021年02月


3753817_s


本記事では入力した値以下の素数を出力するプログラムを紹介します。



素数を求めるプログラム


素数とは1と自分以外に約数を持たない数のことです。

2, 3, 5, 7... などが素数になります。

ある値が素数かどうかプログラムで出力するには下記の関数のように、
「2 ~ ある値 - 1」の数までで割り切ることができる数がなければ素数であると判定することができます。

#include <iostream>

using namespace std;

bool isPrimeNum(int num){
    for (int i = 2; i < num; ++i){
        if (num % i == 0){
            return false;
        }
    }
    return true;
}

上記の関数を使い2~入力値まで順番に素数かどうか判定することで、入力した値以下の素数を全て出力することができます。

int main(void){
    int num;
    cin >> num;

    for (int i = 2; i <= num; ++i){
        if (isPrimeNum(i)){
            cout << i << endl;
        }
    }

    return 0;
}





プログラムを高速化する


先ほど紹介したプログラムは計算量がで効率が良いプログラムとは言うことができません。

そこでここでは先ほどのプログラムを高速化していきます。

まずはisPrimeNum関数を最適化しています。

先ほどの
isPrimeNum関数では「2 ~ ある値 - 1」の数までで割り切ることができる数がなければ素数であると判定していましたが、ある値が素数であるかどうか判定するには「ある値未満の素数」で割ることができるか計算するだけで大丈夫です。

なのでisPrimeNum関数を以下のように書き換えてしまいましょう。


bool isPrimeNum(int num){
    static vector primeNumVec = {2};
    for (auto itr = primeNumVec.begin(); itr != primeNumVec.end(); ++itr){
        if (num % *itr == 0){
            return false;
        }
    }
    primeNumVec.push_back(num);
    return true;
}

primeNumVecというベクターに素数と判定した数をため込んで、入力値がprimeNumVecの中の値で割り切れるかどうか判定します。


これだけでも十分早くなるのですが、main関数にも一工夫加えていきます。

素数は2以外の値は全て奇数なので、for文のiを1ずつ増やしてすべての数を見るのではなく、iを2ずつ増やして奇数だけを見るようにしましょう。

int main(void){
    int num;
    cin >> num;

    cout << 2 << endl;
    
    for (int i = 3; i <= num; i+=2){
        if (isPrimeNum(i)){
            cout << i << endl;
        }
    }

    return 0;
}


これで入力した値以下の素数を出力するプログラムを高速化することができました。


最後に


本記事を通して素数を求めるプログラムの作り方が分かりましたか。

他にもプログラムに関する記事を書いていますので興味のある方はぜひ読んでみてください。







3753817_s


本記事では入力した2個の整数から最小公倍数を求めるプログラムを2パターン紹介します。




「共通して割れる数」を探して、最小公倍数を求めるプログラム


最小公倍数を求めるシンプルな実装は共通して割れる数を元に最小公倍数を求める方法です。

入力値が24と36の場合、数のように共通して割れる数がなくなるまで割っていきます。


aa


共通して割れる数がなくなったら外側の数字をかけていきます。

aa


2 × 2 × 3 × 2 × 3 = 72

これにより24と36の最小公倍数は72だと求めることができます。

これをプログラムで実装していくと以下のようになります。 


#include <iostream>

using namespace std;

int main(void){
    unsigned int a, b, tmp;
    cin >> a >> b;
    if (b > a){
        tmp = b;
        b = a;
        a = tmp;
    }

    unsigned int Lcm = 1;
    int i = 2;
    while(b > i){
        if ((a % i == 0) && (b % i == 0)){
            a /= i;
            b /= i;
            Lcm *= i;
            i = 2;
        }
        else{
            i++;
        }
    }

    Lcm = Lcm * a * b;
    cout << Lcm << endl;

    return 0;
}





最大公約数から最小公倍数を求めるプログラム


上記の方法だとどうしても計算量が多くなります。

そこでここでは、ユークリッド互除法で最大公約数を求めてから、それをもとに最小公倍数を求める方法を紹介していきます。

入力値をaとb、aとbの最大公約数をrとすると最小公倍数は以下の式で求めることができます。


最小公倍数 = a × b ÷ r



ユークリッド互除法については以下の記事で紹介しているので参考にしてください。




最大公約数から最小公倍数を求めるプログラムは以下のとおりです。

#include <iostream>

using namespace std;

int calGcd(int a, int b){
    int tmp;
    if (a < b){
        tmp = b;
        b = a;
        a = tmp;
    }

    while(b != 0){
        tmp = b;
        b = a % b;
        a = tmp;
    }

    return a;
}

int main(void){
    int a,b,gcd, lcm;
    cin >> a >> b;
    
    gcd = calGcd(a, b);
    lcm = a * b / gcd;

    cout << lcm << endl;

    return 0;
}



最後に


本記事をとおして、最小公倍数を求めるプログラムの作り方が分かりましたか。

シンプルに「共通して割れる数」をもとに最大公約数を求める方法もいいですが、ユークリッド互除法で最大公約数を求めてから最小公倍数を求めることで計算量を減らすことができます。

プログラミングになれてきましたらぜひ計算量の小さいコーディングを意識していきましょう。






3753817_s


本記事では入力した2個の整数から最大約数を求めるプログラムを2パターン紹介します。




for文を使ったシンプルな実装


最大公約数を求める一番シンプルな実装はfor文を使って入力された数値の両方で割ることができる、値を見つける方法です。

入力値のうちの大きい自然数をa、小さい自然数をbとします。

2~bまでの数でaとbの両方で割れる最大の数を見つけるプログラムを書けば最大公約数を求めることができます。

サンプルコードは以下の通りです。


#include <iostream>

using namespace std;

int main(void){
    int a,b;
    cin >> a >> b;

    int tmp = 0;
    if (a < b){
        tmp = a;
    }
    else{
        tmp = b;
    }

    int gcf = 1;
    for (int i= 2; i<=tmp; ++i){
        if ((a % i == 0) && (b % i == 0)){
            gcf = i;
        }
    }

    cout << gcf << endl;

    return 0;
}






ユークリッド互除法を使う効率の良い実装


入力値のうちの大きい自然数をa、小さい自然数をbとします。

ユークリッド互除法とは、aをbで割った余りをrとすると、aとbの最大公約数はbとrの最大公約数に等しくなるという法則です。

例えば390と273という数値が入力されたとします。

390 ÷ 270 = 1 あまり 117

これをユークリッド互除法の法則に当てはめると

「390と270の最大公約数 = 270と117の最大公約数」ということになります。

これを割り切れるまで繰り返していくと、割り切れる一つ前の余りの値が最大公約数になります。

ユークリッド互除法を使って最大公約数を求めるサンプルコードは以下のとおりになります。

#include <iostream>

using namespace std;


int main(void){
    int a,b,tmp;
    cin >> a >> b;

    if (a < b){
        tmp = b;
        b = a;
        a = tmp;
    }

    while(b != 0){
        tmp = b;
        b = a % b;
        a = tmp;
    }

    cout << a << endl;
}


コードの長さもループを使って闇雲に求めた方法より少なく、シンプルです。

今回はループを使ってユークリッド互除法を使って最大公約数を求めるプログラムを書きましたが、再起関数を使用することでよりすっきりした実装になります。


最後に


本記事をとおして、ユークリッド互除法を使うことで効率よく最大公約数を求めることができることが分かりましたか。

単純に小さい数から割っていって、最大公約数を求める方法もいいのですが、計算量やコード量を意識してより効率のよい実装を行いましょう。






↑このページのトップヘ