第１話 素数とは？
皆さん、素数って何でしたっけ。
素数の例を挙げると、
２，３，５，７，１１，１３，１７，１９，２３，・・・
どうです。
記憶が蘇ってきましたか。
そうです。１と自分自身でしか割り切れない整数です。
ただし、１は素数ではありません。
では素数の判定はどうしたらよいでしょうか。
例えば、１５１が素数であるかどうか判定せよといわれましたどうしますか。
素数判定の第１は、偶数でないことです。
２以外の素数は、奇数であるからです。
１５１は奇数ですから、その条件をクリアしています。
第２の関門は、ルート１５１（約１２．３)以下の奇数で割っていってすべてで割り切れない、ということです。
ルート１５１（約１２．３)以下の奇数で十分な理由を説明しましょう。
１５を例に取るなら、１５約数は１，３，５，１５です。
そして、１で割った数が１５で、３で割った数が５です。
１と３は当然ルート１５（約３．９）以下です。
残りの相棒は、割った商なので１と３で割り切れる場合当然５，１５で割り切れます。
ですから１５１の場合、ルート１５１以下の奇数すなわち１１以下で割り切れなければ、
１５１を割り切る整数は、１と１５１以外は存在しないことになります。
ルート１５１は、Math.sqrt(151)で求まります。
さて、皆さんプログラムを組んでください。
解答コード例は、３０行下。
解答コード例
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)+"個見つかりました。");
}
}
実行画面例
実はこのプログラムは、改善の余地があります。
９９１が素数であるかの判定は、ルート９９１（約３１．５）以下の奇数ではなく、素数で割れば判定できます。
つまり、３，５，７，９，１１，１３，１５，１７，１９，２１，２３，２５，２７，２９，３１の内ピンクの部分で割るのは不要で時間を無駄にしています。
見つかった素数は、配列に蓄えてありますので、それを利用して寄り効率的なプログラムに変更してください。
時間で思い出しました。素数探索時間を計測できるようにも変更しましょう。
第１７講第７話へ 第２話へ
VB講義へ
ＶＢ講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第１部
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第２部
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第３部
