第６話 ２以外の偶数を探索対象から外す
改良例
#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();
f();
ow=clock();
cout<<"素数生成にかかった時間は"<<(double)(ow-hj)/1000<<"秒です。"<<endl;
cout<<"プロジェクト終了"<<endl;
}
void f(){
int i,j;
s[0]=2;
cn=1;
cout<<2<<" ";
for(i=3;i<10000001;i+=2){
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;
double w;
w=sqrt((double)i);
for(j=0;j<cn;j++){
if(i%s[j]==0)return(0);
if(s[j]>w)return(1);
}
}
参考ダウンロード添付ファイル改良１
実行結果
前の実行結果
この結果を見ると、速くなったように見えますが、
何回も実験してみると、結果が逆になってしまうこともあります。
実験誤差が結構あります。
そこで、両者の差をより正確に見るために、
第５話と第６話のソースを改良し、
第５話実験ファイル 第６話実験ファイル
１００回の平均値を取って実験してみると、
第６話ファイル実験結果
第５話ファイル実験結果
確かに少しは速くなったようです。
この後、３以外の３の倍数を外すプログラムを考える予定でしたが、
偶数を外す実験から、効果は期待できそうもありません。
素数探索の高速化・・・
これは意義のある研究です。
RSA理論による暗号が素数を暗号鍵にしているからです。
セキュリティを万全にするためには、
ハッカーが考える方法を、
事前に予測して、潰しておく必要があるからです。
高速化する１つの方法は、
第18講で学ぶ予定になっているマルチスレッドプログラミングです。
これは、並列処理です。
量子コンピュータも並列処理によって高速化を実現するものです。
シングルスレッド・・・直列処理
マルチスレッド ・・・並列処理
シングルスレッドって何？
直列処理とは？
マルチスレッド？？
並列処理・・・！？
興味のある方、講義を続けて読みましょう。
シングルスレッドでは、
今のところこれ以上高速化するアイデアは、
私にはありません。
ですから、高速化は第18講に委ねて第16講を終了することにします。
第５話へ 第17講第１話へ
eclipse c++ 入門講義第１部へ
魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第１部
eclipse java 入門
java 入門 サイト 基礎から応用まで
VC++ C言語 C++ 入門 初心者 基礎から応用まで
本サイトトップへ
