第18講 素数・完全数・友愛数・フィボナッチ数列探索
第1話 素数とは?
皆さん、素数って何でしたっけ。
素数の例を挙げると、
2,3,5,7,11,13,17,19,23,・・・
どうです。
記憶が蘇ってきましたか。

そうです。1と自分自身でしか割り切れない整数です。
ただし、1は素数ではありません。

では素数の判定はどうしたらよいでしょうか。
例えば、151が素数であるかどうか判定せよといわれましたどうしますか。

素数判定の第1は、偶数でないことです。
2以外の素数は、奇数であるからです。
151は奇数ですから、その条件をクリアしています。
第2の関門は、ルート151(約12.3)以下の奇数で割っていってすべてで割り切れない、ということです。
ルート151(約12.3)以下の奇数で十分な理由を説明しましょう。
15を例に取るなら、15約数は1,3,5,15です。
そして、1で割った数が15で、3で割った数が5です。
1と3は当然ルート15(約3.9)以下です。
残りの相棒は、割った商なので1と3で割り切れる場合当然5,15で割り切れます。
ですから151の場合、ルート151以下の奇数すなわち11以下で割り切れなければ、
151を割り切る整数は、1と151以外は存在しないことになります。


ルート151は、Math.sqrt(151)で求まります。
さて、皆さんプログラムを組んでください。
解答コード例は、30行下。




















解答コード例
import java.io.*;
class sh{
  static int[] x=new int[100000];
  static int n,cn;
  public static void main(String args[])throws IOException{
    BufferedReader u=new BufferedReader(new InputStreamReader(System.in));
    System.out.println("探索範囲を入力してください。");
    System.out.print ("探索範囲=");
    int i;
    n=Integer.parseInt(u.readLine());
    x[0]=2;
    cn=0;
    for(i=3;i<n;i+=2){
      if(f(i)){
        cn++;
        x[cn]=i;
      }
    }
    g();
  }
  public static boolean f(int a){
    int i;
    for(i=3;i<=(int)(Math.sqrt(a));i+=2){
      if(a%i==0)return(false);
    }
    return(true);
  }
  public static void g(){
    int i;
    for(i=0;i<=cn;i++){
      System.out.print(x[i]+" ");
      if(i>0 && i%10==0)System.out.println();
    }
    System.out.println();
    System.out.println("素数が"+(cn+1)+"個見つかりました。");
  }
}
実行画面例
入門


実はこのプログラムは、改善の余地があります。
991が素数であるかの判定は、ルート991(約31.5)以下の奇数ではなく、素数で割れば判定できます。
つまり、3,5,7,,11,13,15,17,19,21,23,2527,29,31の内ピンクの部分で割るのは不要で時間を無駄にしています。
見つかった素数は、配列に蓄えてありますので、それを利用して寄り効率的なプログラムに変更してください。
時間で思い出しました。素数探索時間を計測できるようにも変更しましょう。

第17講第7話へ 第2話へ

戻る

VB講義へ
VB講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座

初心者のための世界で一番わかりやすいVBA入門講義(基礎から応用まで)
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第1部
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第2部
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第3部