第16講 素数探索
第5話 奇数ではなく素数で割って素数判定をする
前話解答例
#include<iostream>
#include<math.h>
#include <time.h>
using namespace std;
void f();
char sh(int i);
int s[1000000],cn;
void main(){
   clock_t hj,ow; //clock_t型の宣言、プログラム開始時間を取得するための変数
   hj=clock();
   cn=0;
   f();
   ow=clock();
   cout<<"素数生成にかかった時間は"<<(double)(ow-hj)/1000<<"秒です。"<<endl;
   cout<<"プロジェクト終了"<<endl;
}
void f(){
   int i,j;
   for(i=2;i<100001;i++){
     if(sh(i)==1){
        s[cn]=i;
        if(cn%10==0 && cn>0)cout<<endl;
        cn++;
        cout<<i<<" ";
     }
   }
   cout<<endl<<"素数は"<<cn<<"個できました。"<<endl;
}
char sh(int i){
   if(i==2)return(1);
   if(i==3)return(1);
   if(i%2==0)return(0);
   int j;
   for(j=0;j<cn;j++){
     if(i%s[j]==0)return(0);
   }
}
参考ダウンロード添付ファイル
実行結果
q
前の実行結果
y
確かに速くなりましたが、わずかしか差がありません。
そこで1から100000までではなく、
1から10000000までに変更して実験すると、
n
e
と確かに差が出てきます。
とはいえ、さほどの差ではありません。
より高速化するのはどうしたらよいでしょうか。
2以外の偶数は、素数でないことを考えれば、
void f(){
   int i,j;
   for(i=2;i<100001;i++){
     if(sh(i)==1){
        s[cn]=i;
        if(cn%10==0 && cn>0)cout<<endl;
        cn++;
        cout<<i<<" ";
     }
   }
   cout<<endl<<"素数は"<<cn<<"個できました。"<<endl;
}
には改良の余地がありそうです。
2以外の偶数は、
はじめから探索対象から外すプログラムを考えてみて下さい。


第4話へ
 第6話へ

a

eclipse c++ 入門講義第1部へ

魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義(基礎から応用まで)
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第1部
eclipse java 入門
java 入門 サイト 基礎から応用まで
VC++ C言語 C++ 入門 初心者 基礎から応用まで
本サイトトップへ