【Java アルゴリズム修行④】素数判定

###素数判定

素数の意味がピンとこなかったので、もはやアルゴリズム以前の問題じゃないのか。。と思いましたが
素数を知らないことをこの瞬間に知れたんだ！と前向きに捉えつつ、まずは調べてみました！

素数 とは、「1とその数以外の正の約数を持たない自然数」を指す

ふむ。。 1と自身以外で割り切れなければ素数らしいです。
例えば7だと、7÷2も7÷3も7÷4も7÷5も7÷6も割り切れないから素数だよ　って感じみたいですね。

入力された値が素数かどうかの判定をするとなると。。

• その数が1以下かどうか（1以下はまず素数じゃない）
• その数が1と自身以外の数で割り切れるかどうか

を判定すれば良さそうです。

alog.java

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int target = sc.nextInt();
        //入力値がそもそも1以下であれば素数ではないので弾く
        if (target <= 1){
            System.out.println(target + "は素数ではありません");
            return;
        }

        for (int i = 2; i < target; i++){
            // 2~入力値未満の間で割り切れてしまえば素数ではない判定
            if(target % i == 0){
                System.out.println(target + "は素数ではありません");
                return;
            }
        }
        //割り切れない場合は素数判定
        System.out.println(target + "は素数です");
    }
}

入力値に対して、まず最初に1以下であれば素数ではないのが確定なので弾いてしまいましょう。
その後、入力値を[2~入力値未満]で繰り返し除算し、もし割り切れない場合は素数だね！という流れで書いてみました。

条件さえ整理できればそれほど難しくなさそうですね！（成長を感じます）

入力値までの素数を出力してみる

調子に乗って、今度は2~入力値まで（1以下は素数ではないので）に存在する素数を出力するプログラムを作ってみます。
下記判定条件を3~入力値まで存在する数だけ行うことになるので2重ループを使うことになりそうですね。。（プログラムが動いた後だからこんな余裕の口調になってます）

• その数が1以下かどうか
• その数が1と自身以外の数で割り切れるかどうか

algo.java

import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int target = 0;

    // 1以下の数字には素数は存在しないので、2以上の値が入力されるまで待つ
    do {
      System.out.println("2以上の数を入力してください");
      target = sc.nextInt();
    } while (target < 2);

    // 2は1と自身の数以外では割れないので決め打ちで出力する
    System.out.println("2は素数です");

    // 3 ~ 自身の数の間の奇数のみで繰り返し素数判定を行う
    for (int i = 1; i <= target; i += 2) {
      // 1か自身の数以外で割り切れれば素数ではない
      for (int j = 2; j < i; j++) {
        if (i % j == 0) {
          break;
        } else if (j == i - 1) {
          System.out.println(i + "は素数です");
        }
      }
    }
  }
}

入力値が2以上の数でなければ素数は表示されないので、do-while文で(targe < 2)
として入力値が1未満であれば再度入力を促すようにしました。

2以上であれば、2だけは決め打ちで出力し、それ以降は繰り返し処理で、それぞれ素数判定を行います。
入力値自身の素数判定だけでなく、3〜入力値までの数それぞれに判定が必要になるので、2重ループを使用しました。
（偶数は2で割れるため、奇数のみで判定するように更新文にて、i+=2を行っています。）

その数が1以下かどうかという判定は先のdo-while文で終わっているので、
その数が1と自身以外の数で割り切れるかどうかのみを2重目のループで判定しています。

if(i % j == 0)ここのiは素数か否かを判定したい数そのもので、jは3~判定したい数までをインクリメントして除算を行い、余りが0であれば割り切れてしまっている（その数は素数ではない）ので、その時点でbreak文を使って2重目のループごと抜けるようにしました。

else if(j == i - 1)では、全く割り切れずに自身の数の直前まで繰り返せた場合を想定しているので、
そこまできたら素数だね！ということで素数である旨を出力しています。

個人的に、最後の判定部分がちょっとブサイク気味なので2重目の条件文とかでどうにかならないか試行錯誤中です。。

###さらにスマートに

algo.java

import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int counter = 0;
    int i = 0;
    for(int n = 2; n <= 1000; n++){
        for(i = 2; i < n; i++){
            counter++;
            if (n % i == 0) {
                break;
            }
         }
        //どの数でも割り切れることなく、自身の数まできたときは素数となる
        if(n == i){
            System.out.println(n + "は素数です");
            }
        }
    System.out.println("除算回数は" + counter);
  }
}

入力値ではなく、1000以下の数として決め打ちではありますが、素数判定が個人的にかなりスマートな印象ですね！
2重目のループで２〜自身の数未満の間のどれでも割り切れなかった場合は という部分をif(n == i)で判定することでよりすっきりできた気がします。。　 ここでの除算回数は78,022回。。！（ターミナル上ではほぼ一瞬ですが笑）

algo.java

import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int timer = 0;
    //得られた素数の数
    int counter = 0;
    //1000の偶数を除いた数の500で配列を生成する
    int [] prime = new int[500];
    //1要素目には既定の素数、2を代入する
    prime[counter++] = 2;
    int i = 0;
    //2は既に代入したので、3~1000の間で、偶数のもののみで素数判定を行う
    for(int n = 3; n <= 15; n +=2){
        // 素数だけで除算を行う
        for(i = 1; i < counter; i++){
            timer++;
            if (n % prime[i] == 0) {
                break;
            }
         }
        //どの数でも割り切れることなく、自身の数まできたときは素数配列に代入する
        //素数の個数と、繰り返す回数が一致していれば素数の最後まで除算をしたということになる
        if(counter == i){
            prime[counter++]= n;
            }
        }
    for(int a : prime){
        if(a == 0) break;
        System.out.println(a + "は素数です");
    }
    System.out.println("除算回数は" + timer);
  }
}

これは自力ではありませんが、より効率的に行う考え方として参考に載せておきます！
奇数だけで繰り返すのは同じですが、全ての値で除算するのではなく、それまでの素数で割り切れるかを確かめるというものです。素数でも割り切れなければ確実に素数であるので、これで除算回数は 14,622回まで減るのが確認できました。。！（凄まじい。。）

素数だけの配列を最初に組んでしまい、その素数の要素数まで割り切れなければ、判定対象の数字も素数とみなし、配列に代入することでより効率的になると言った感じですね。

###学んだこと

• 条件を明確にして、どこまでをif文判定するのかを見極める
• break文を使ってループごと抜ければ、余計な繰り返し処理を省ける
• 無駄な除算など、削れるものがないか偶数・奇数など条件を絞れないか試してみるのは大事

これまでは全てをゴリ押しif判定していましたが、do-while文で最初の入力値を弾くことによって無駄な処理を行わずに済むことが分かりました！do-whileは使い所ないのでは。。と思っていましたが、判定する前に処理を挟めるのは入力値の判定と相性がいいのかもしれません。。

break文、continue文も有効活用して余計な処理はなるべく省くことも意識していきたいと思いましたし、無駄なものが削れないか、条件を絞れないかなどの閃きは量をこなしていけば身についてくれる、、と信じて引き続き頑張っていきます！