第13講 素数探索
第８話 素数探索プログラムVer.3
実行結果
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
〜
199211 199247 199261 199267 199289 199313 199321 199337 199343 199357
199373 199379 199399 199403 199411 199417 199429 199447 199453 199457
199483 199487 199489 199499 199501 199523 199559 199567 199583 199601
199603 199621 199637 199657 199669 199673 199679 199687 199697 199721
199729 199739 199741 199751 199753 199777 199783 199799 199807 199811
199813 199819 199831 199853 199873 199877 199889 199909 199921 199931
199933 199961 199967 199999
素数が1から200000の間に17984個ありました。
素数探索にかかった時間は0.031000秒です。
プロジェクト終了
を実現するプログラム例
#include<stdio.h>
#include<time.h>
char f(int a);
int main(){
int i,cn;
clock_t hj,ow;
hj=clock();
cn=0;
for(i=1;i<200001;i++){
if(f(i)){
printf("%d ",i);
cn++;
if(cn%10==0)printf("\n");
}
}
printf("\n");
printf("素数が1から200000の間に%d個ありました。\n",cn);
ow=clock();
printf("素数探索にかかった時間は%f秒です。\n",(double)(ow - hj) / CLOCKS_PER_SEC);
printf("プロジェクト終了\n");
return(0);
}
char f(int a){
int w,i;
w=sqrt(a);
if(a==1)return(0);
if(a==2)return(1);
if(a%2==0)return(0);
for(i=3;i<=w;i+=2){
if(a%i==0)return(0);
}
return(1);
}
素数探索プログラムVer.3
さて、第13講最後の改善です。
あくまで第13講内の最後の改善です。
素早く素数を探索することは、
セキュリティを高めるために重要な研究ですから、
探索には様々な工夫がされています。
セキュリティを破るハッキングのためにではなく、
ハッキングされないために、
つまり、守るために素数探索や因数分解プログラムの研究は、
大切な研究なのです。
ですから、いろいろと研究されています。
小学生からエンジニアまでのc言語入門でも、
第５部辺りで、巨大素数や巨大整数の因数分解も、
研究主題になります。
さて、最後の改善とは、２について述べたこと
２，４，６，８，１０，１２，１４，１６，１８，２０，２２，２４，２６，２８，・・・
が、実は３，５，７，１１，１３，・・・等にも言えるのです。
３，９，１５，２１，２７，３３，３９，・・・
５，１５，２５，３５，４５，５５，・・・
７，２１，３５，４９，６３，・・・
１１，３３，５５，７７，・・・
これらで意味のある割り算は、
最初の数だけです。
３で割り切れなければ、
９や１５などで割り切れないのは当たり前の話です。
ですから、99971 が素数であるかどうかを確認するために、
９，１５，２１，２７，３３，３９，・・・
１５，２５，３５，４５，５５，・・・
２１，３５，４９，６３，・・・
３３，５５，７７，・・・
等で割ることはまったく無駄な行いです。
ところで、
２，４，６，８，１０，１２，１４，１６，１８，２０，２２，２４，２６，２８，・・・
３，９，１５，２１，２７，３３，３９，・・・
５，１５，２５，３５，４５，５５，・・・
７，２１，３５，４９，６３，・・・
１１，３３，５５，７７，・・・
の黒の数字って何ですか。
そうです。
素数です。
そうするとaが素数であることを確認して行くには、
aの平方根以下の素数で割っていって、
割り切れるかどうか、すなわち、
割ったときに余りが出るかでないか、を調べれば良いのです。
その時点まで生成した素数を貯めておくには、
配列を用意しておく必要があります。
配列自体を引数にして送るということは、
次の講のテーマですが、
先取りして説明しておきましょう。
mainにおいて、
int s[10000];
によって、素数を収納する配列を宣言しておいて、
for(i=1;i<100001;i++){
if(f(i,s)){
とすれば、配列を引数にして社員fに渡すことが出来ます。
受け取る社員の方は、
char f(int a,int s[10000])としておけば、
配列を受け取ることが出来ます。
プロトタイプ宣言も
同様に、
char f(int a,int s[10000]);
としておくことを忘れないようにしましょう。
では取り組んで下さい。
Ver.4の実行画面
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
〜
198943 198953 198959 198967 198971 198977 198997 199021 199033 199037
199039 199049 199081 199103 199109 199151 199153 199181 199193 199207
199211 199247 199261 199267 199289 199313 199321 199337 199343 199357
199373 199379 199399 199403 199411 199417 199429 199447 199453 199457
199483 199487 199489 199499 199501 199523 199559 199567 199583 199601
199603 199621 199637 199657 199669 199673 199679 199687 199697 199721
199729 199739 199741 199751 199753 199777 199783 199799 199807 199811
199813 199819 199831 199853 199873 199877 199889 199909 199921 199931
199933 199961 199967 199999
素数が1から200000の間に17984個ありました。
素数探索にかかった時間は0.015000秒です。
プロジェクト終了
Ver.1からVer.4までの時間をすべて載せておきましょう。
2.388000秒→1.234000秒→0.031000秒→0.015000秒
初期バージョンに比べて、約１６０倍の速さになりました。
まさに長足の進歩です。
初心者のための excel 2016 マクロ VBA 入門講義 基礎から応用まで
vc++ c言語 c++ 入門 初心者 基礎から応用まで
eclipse c++ 入門
魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第１部
eclipse java 入門
java 入門 サイト 基礎から応用まで
本サイトトップへ
