面接常備テーマ---素数の判断

ブログ園にいる私の文章ですが、皆さんにとってちょっと役に立つかもしれないと思い、貼ってきました.
来年から就職活動を始めるので、現在準備中なので、データ構造の基礎知識や面接問題を補い、不定期に整理しています.私は発見して、素数の判断は1つのとてもよくあるアルゴリズムで、基本的に、私が見た多くの問題はすべて素数の判断に関連しなければならなくて、例えば、1024から687432のすべての素数の和、あるいは720のN次方の中で、どれらの数が素数なのかなど、大体素数の問題目に関連して、核心の問題はどのように素数を判断するかを理解することです.
では、素数をどう判断するのか.素数とは、自身と1でしか割り切れない自然数を指し、よく見られる比較的実現しやすいアルゴリズムは、この数Nを<=Nのすべての素数で割り出し、いずれも割り切れない場合、Nは素数である.
コードを書き始めました

 boolean isPrime(int number) {
        boolean isPrime = true;
        for (int i = 2; i <= Math.sqrt(number); i++) {
              if (number % i == 0) {
                  isPrime = false;
               }
         }
         return isPrime;
} 

次にテストを行います.

public class test{
  public static void main(String[] args){
      for(int i = 0; i < 100; i++){
         if(isPrime(i)){
           System.out.println(i + "   ");
         }
      }
  }
}

出力結果は次のとおりです.
2は素数3は素数5は素数7は素数11は素数13は素数17は素数19は素数23は素数29は素数31は素数37は素数41は素数43は素数47は素数53は素数59は素数61は素数67は素数71は素数73は素数79は素数83は素数89は素数97は素数
コードは暗記する必要はありません.アルゴリズムを知っていれば、プログラマーは欲しいコードを書くことができます.
だから、ここで私はもう一度アルゴリズムを繰り返します:1つの数Nさえあれば、[2,sqrt(N)]の区間内で、それを除去することができる数は何もありません.それは素数です.どうして2ですか.0を除数とすることは不可能なので、どの数でも1で割ることができます.
素数に関する判断はまだ小さな問題で、上記のように具体的な問題と結びつける必要があります.そして、これらの問題には罠が潜んでいます.例えば、以下の問題です.
720のN次方のうち、素数は何個ありますか?
このような問題は簡単そうに見えますが、私たちはすぐに作ることができます.
コードを見てください:

public class test{
      int number = 1;
      int counter = 0;
      for(int i = 0; i < Integer.MAX_VALUE; i++){
           number *= 720;
           if(isPrime(number){
              counter++;
           }
      }
      System.out.println(counter);
}

ここまでやって、みんなはきっと問題を見たことがあると信じています:私たちはどのようにそのNを確定するべきですか?ここでは正の整数の最大値を使用していますが、必ずエラーが発生することを知っています.これは整数の最大範囲を絶対に超えているので、Nを確定することがこの問題の鍵です.

int getRange(int number, int divisor) {
      int range = 0;
      while ((number / divisor != 0)) {
           range++;
           number = number / divisor;
       }
      return range;
}

は、次にテストを行います.

public static void main(String[] args) {
      int number = 1;
      int divisor = 2;
      int range = getRange(Integer.MAX_VALUE, divisor);
      for (int i = 0; i < range; i++) {
            number *= divisor;
            if (isPrime(number)) {
                System.out.println(number + "   ");
             }
       }


}

私たちの判断数がjava整数の範囲内であることを確認する必要があります.
ここではjavaの整数範囲:-2の31次から2の31次まで1を減らします.