第５話 １次元配列利用による素数探索解答例
コード例
#include<iostream>
#include <math.h>
using namespace std;
using namespace System;
void f();
int main(){
f();
}
void f(){
int i,j,a[100000],h,cn;
a[0]=2;
cn=1;
cout<<a[0]<<" ";
for(i=3;i<10000;i++){
h=1;
for(j=0;j<10000;j++){
if(a[j]>sqrt((double)i))break;
if(i%a[j]==0){
h=0;
break;
}
}
if(h==1){
a[cn]=i;
cout<<a[cn]<<" ";
cn++;
}
}
cout<<endl;
cout<<"素数が"<<cn<<"個ありました。"<<endl;
}
実行例
解説
いろいろ？マークが浮かんでいますよね。
１行１行詳しく解説していきましょう。
まず、cnの役割は何でしょうか。
cnはカウンタです。
何をカウントしているかといいますと、素数の個数です。
a[0]=2;
cn=1;
は２は素数ですので、この次元で１個ということです。
cout<<a[0]<<" ";
は２を表示しています。
for(i=3;i<10000;i++){
h=1;
for(j=0;j<10000;j++){
if(a[j]>sqrt((double)i))break;
if(i%a[j]==0){
h=0;
break;
}
}
if(h==1){
a[cn]=i;
cout<<a[cn]<<" ";
cn++;
}
}
は３から１００００までの整数の中にある素数を探させています。
h=1;
のhは１なら素数であり、０なら素数でないの意味をもたせています。
初めは１にしておいて、ひとつでも割りきれる素数が見つかったらh=0にして、
for(j=0;j<10000;j++){
if(a[j]>sqrt((double)i))break;
if(i%a[j]==0){
h=0;
break;
}
}
を強制的に終了させる仕様になっています。
強制的に終了させられず、for文が通常終了した場合h=1は書き換えられませんので、
if(h==1){
a[cn]=i;
cout<<a[cn]<<" ";
cn++;
}
が遂行されます。
気をつけてほしいことはcn++;の位置です。
うっかりすると
if(h==1){
cn++;
a[cn]=i;
cout<<a[cn]<<" ";
}
とやってしまいます。
最初の３は素数です。これは２個目ですからa[1]=3です。
添え字が０から始まるため１個ずれることに注意しましょう
ですから後からのカウントである
if(h==1){
a[cn]=i;
cout<<a[cn]<<" ";
cn++;
}
でなければならないのです。
さて、最初はfor文の上限は１００００ぐらいにしましたが、
１０００００、１００００００などでも実験しましょう。
１０００００の場合は
ですし、１００００００の場合は
です。７８４９８個の素数をたちどころに求めてしまいます。
コンピュータ恐るべしですね。
さて、次話では３次元配列を利用して、次のような各学期別成績一覧表を作ることにしましょう。
