第５話 奇数ではなく素数で割って素数判定をする
前話解答例
#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);
}
}
参考ダウンロード添付ファイル
実行結果
前の実行結果
確かに速くなりましたが、わずかしか差がありません。
そこで１から１０００００までではなく、
１から１０００００００までに変更して実験すると、
と確かに差が出てきます。
とはいえ、さほどの差ではありません。
より高速化するのはどうしたらよいでしょうか。
２以外の偶数は、素数でないことを考えれば、
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;
}
には改良の余地がありそうです。
２以外の偶数は、
はじめから探索対象から外すプログラムを考えてみて下さい。
第４話へ 第６話へ
eclipse c++ 入門講義第１部へ
魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第１部
eclipse java 入門
java 入門 サイト 基礎から応用まで
VC++ C言語 C++ 入門 初心者 基礎から応用まで
本サイトトップへ
