Zenn
📌

アルゴリズムをコードにする練習1：素数かどうか判定する

2020/11/18に公開1件
アルゴリズム
tech

素数の判定法

素数というのは、1より大きい整数で、1と自分自身以外では割り切れない数のことです。
素数かどうか判定するには、まず2で割って割り切れるかどうか、次に3で割り切れるかどうか、と1ずつ割る数を増やしながら、その数自身-1まで割っていっても割り切れなければ素数、どこかで割り切れたら素数ではない、ということになります。
もう少し効率よく求める方法がありますが、今回はシンプルなこの形で考えます。

素数判定のアルゴリズム

ここでは、話を単純にするために、指定した数値は1より大きくて、計算して桁あふれしてしまうほど大きな数字ではないという前提にします（実際の業務では、そこの数値チェックはロジックではなくて、UI側でするべきだと思います）。

  1. 数値かどうか判定する値をn、割る数をiとする
  2. iが2から始まってn未満まで1ずつ増えていく繰り返しを設定する
  3. 2の繰り返しの中でnをiで割った余りを求める
  4. 3の余りが0なら素数ではないので繰り返しを終了する
  5. 3の余りが0でないなら繰り返しを続け、最後まで繰り返しても0にならなければ素数

素数判定アルゴリズムのフローチャート

というアルゴリズムをフローチャートにするとこうなります。

長方形と台形の組み合わさった形が繰り返し、ひし形が条件分岐です。

ここでは、判定する数nを引数として受け取って、素数なら真、素数でないなら偽を返すものを考えます。これなら、前回出てきたスコープや戻り値で悩むことはありません。

コードの形

javaScript

これをJavaScriptの関数にすると、次のようになります。

function isPrime(n){
    let ret = true;
    for(i=2; i<n; i++) {
        if(n % i == 0) {
            ret = false;
	    break;
        }
    }
    return ret;
}

フローチャートとちょっと違い、あらかじめ戻り値にtrueを設定しておいて、素数でないことが判明した時点でfalseに変更します。

Java

JavaもJavaScriptと同様です。C++やC#もほぼ同じ形に書けます。

boolean isPrime(int n){
    boolean ret = true;
    for(int i=2; i<n; i++){
        if(n % i == 0) {
            ret =  false;
	    break;
        }
    }
    return ret;
}

C言語

cでは真偽値を表す型はないので、素数なら1、素数でないなら0を返します（実際のコードだと、defineでTRUEに1、FALSEに0を設定するでしょう）。

int is_prime(int n){
    int i , ret = 1;
    for(i=2; i<n; i++) {
        if(n % i == 0) {
            ret = 0;
        }
    }
    return ret;
}

Python

Pythonだと、以下の形になります。

def isPrime(n):
    for i in range(2,n):
        if n % i == 0 :
            ret = False
            break
    else:
        ret = True
    return ret

Pythonの場合は、繰り返しをbreakで終了したかどうかを繰り返しのブロックのあとのelseで判定できるので、戻り値にあらかじめTrueをセットしておくのではなく、繰り返しが最後まで実行されたときだけTrueになるように書けます。これがいちばんフローチャートに沿った形になりますね。

まとめ

言語の特徴によって、フローチャート通りにならなかったところもありますが、これはフローチャートを実装言語を想定せずに描いたせいなので、実際には最初から言語に合わせた実装イメージを持って流れを考えます。
今回のコードを、呼び出し側も合わせて書いたコードは、
https://github.com/riko111/IntroductionToAlgorithm/tree/main/algo1
にアップしています。

Discussion