ｂool

素数を求めるプログラムを作りました。
素数か、そうでないかを１か０で区別していたのですが、
よりメモリを効率よく使いたいため、booleanを使ったらどうだという案をいただきやってみたのですが、エラーが出てしまいました。
このプログラムの何がいけないのですか？

#include<stdio.h>
#include<stdbool.h>
#define n 250000
main(){
int i,p,k,w,np,s;
bool pn[n];


np=0;
for(i=0;i<n;i++){
pn[i]=false;
}

for(i=0;i<=n;i++){

if(pn[i]==false){
p=3*i+5-(i%2);
w=2*p;
for(k=i+w;k<=n;k+=w){
pn[k]=true;
}

s=5*i+7-2*(i%2);
for(k=s;k<n;k+=w){
pn[k]=true;
}

np++;
}
}

printf("%10d",np+2);
}

No.5 ベストアンサー 回答者： MiracleCat 回答日時： 2007/10/04 02:40

ご説明ありがとうございます。

どういう意図で組まれたのかようやく納得できました。
が、当方そこまでの理解力が無かったので、純粋にp=iの関係と考えて素数が求まっているように見えなかったというだけです。2の倍数・3の倍数を抜いて計算するという考え方は正しいと思います。（私も以前に2の倍数を除いたエラトステネスの篩なら組んだ事があります。懸賞問題向けだったのですがエラトステネスの篩での応募多数のため予め2の倍数を除いたものは「素数の計算を一部省略している」という理由で不正解とされた不本意な結果でしたが。）

残念ながら、作成されたプログラムのアルゴリズムが正しいか否かは私にはすぐには判断できません。
ただ、少なくとも配列pnの範囲をオーバーしたアクセスがあるのは確かなのでpnを１つ大きく作成するか、for 終端条件の見直しは必要かと思います。

No.4 回答者： MiracleCat 回答日時： 2007/09/30 02:58

まず、他の方も答えていますが bool は一般的なコンパイラは int 等で実装されているため余り記憶領域の節約にはなりません。

No.2の方のようにビットマップを使うべきでしょう。
あと、上記プログラムは上から3番目のforの停止条件がk<=nとなっていて、k=nとなるケースがあり配列pn[n]の領域外アクセスが発生してしまいます。k<nとすべきです。

ただ、上記プログラムを修正したとしても素数を求めているようには思えませんし結果も間違ってます。エラトステネスの篩(ふるい)的なアプローチのようにも見えますがどうなのでしょうか？（エラトステネスの篩になるよう改造してみましたがここに出してしまうとご本人の勉強にならないと思いますので伏せておきます。）

この回答への補足

エラトステネスの篩の応用バージョンのつもりです。
エラトステネスの篩で、予め２と３の倍数をぬいてしまい、篩にかけることで、メモリ使用率を減らそうという目的でつくりました。

まず、添え字iと、対応する自然数pの関係を考える。
普通に考えた時のプログラムでは、p=i、
２の倍数だけを除いたプログラムではp=2*i+3の関係があった。
２，３の倍数を除いたプログラムでは・・・

添え字i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
自然数p 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49

添え字iが偶数（０も含む）の時は　　ｐ＝３＊i＋５
添え字iが奇数の時は　　　　　　　　ｐ＝３＊i＋４　　
の関係があることがわかる。さらに、「iが偶数の時０、奇数の時１になる式」（i%2）を使って、ｐ＝３＊i＋５－（i%2）でまとめられる。

次に、倍数を消していく作業について考える。
添え字iが偶数の時、奇数の時をそれぞれ別々の数列で考えると、どちらも公差６の等差数列になっていることがわかる。

iが偶数 5 11 17 23 29 35 41 47 53
iが奇数 7 13 19 25 31 37 43 49

そこで、例えば５の倍数を消していく作業について考えると、偶数数列においては５から始めて５番目ごとが５の倍数になっているのでそれらを消せばよいことがわかる。つまり、実際（奇数偶数を分けないで考える）は、２×５＝１０ごとに消せばいいことがわかる。奇数数列においては、最初に５の倍数がでてくる、２５から始めれば良い。この２５という数字はs=5*i+7-2*(i%2)で求められる（この式については最後に述べる）。
つまり、ｐから始めて２＊ｐごと、ｓ=5*i+7-2*(i%2)から始めて２＊ｐごとに消していくことにより、倍数を消していく作業が完了する。
３、プログラムについて
１）ｐｎ[i]すべてに１をいれる
２）i=0から指定された数を超えるまで以下の作業を繰り返す
　2-1）ｐｎ[i]の値が１ならば、iに対応する自然数pは素数であるので
　　　A）ｐは残して２＊ｐ以降、２＊ｐごとにpn[i]の値に０を入れる
　　　B）Sから始めて、２＊ｐごとにpn[i]の値に０を入れる
　2-2）ｐｎ[i]の値が０ならば、iの値を１増やす


４、補足ｓ＝5*i+7-2*(i%2)について
２と同様「５」を例にとって考える。まず、５自身は偶数の数列にいるので、偶数の数列において５ずつ消していけば、５の倍数は消えていった。次に奇数数列の２５については、このプログラム自身が２と３の倍数を抜いて考えているのだから、５×２＝１０（２の倍数）、５×３＝１５（３の倍数）、５×４＝２０（２の倍数）は現れないはずである。よって５×５＝２５が最小であることがわかる。ここで疑問に思うのが、ｐと５＊ｐとは添え字の奇数・偶数が必ず異なるのか？ということである。
しかし、実際に５を例にとって考えると、５と２５の添え字の奇数・偶数は異なっている。幸い、ｐと５＊ｐとは添え字の奇数・偶数が必ず異なることが証明できるのである。

一般に、添え字iが偶数である自然数ｐはｐ=3*i+5=3*(2*h)+5=6*(h+1)-1という形で表せ、
また、添え字iが奇数である自然数ｐはｐ=3*i+4=3*(2*h+1)+4=6*(h+1)+1という形で表すことが出来る。

ここで、添え字iが偶数である自然数ｐについては、5*p=(6-1)(6*(h+1)-1)=6(5(h+!)-1)+1となり、5*pにあたる添え字iは奇数であることが証明できた。
また、添え字iが奇数である自然数ｐについては、5*p=(6-1)(6*(h+1)+1)=6(5(h+!)-1)-1
となり、5*pにあたる添え字は偶数であることが証明できた。
以上により、ｐと５＊ｐとは添え字の奇数・偶数が必ず異なることが証明できた。
よって、同じ系列の出発点にはｐ自身、別の系列の出発点には、５*pが使える。

しかし、ｐや５＊ｐは対応する自然数の値であって添え字の値ではない。
ここで５＊ｐの添え字sについて考えるP=3*i+5-(i%2)より
5*p=5(3*i+5-(i%2))=3*(5*i+7-2*(i%2))+5-(1-(i%2))
=3*(5*i+7-2*(i%2))+5-(s%2) (s%2)=1-(i%2)より
よって、s=5*i+7-2*(i%2)とおけば、5*p=3*s+5-(s%2)が成り立つ。

・・・という考えのもとこのプログラムをつくったのですが、考え方が根本的にまちがっているのでしょうか？

補足日時：2007/09/30 18:15

No.3 回答者： koko_u_ 回答日時： 2007/09/28 23:28

素数がまったく判定できていないような気がするのは私だけでしょうか？

No.2 回答者： Oh-Orange 回答日時： 2007/09/28 22:12

★『stdbool.h』では『_Bool』が予約語です。

・『bool』は予約語ではないのでエラーになったと思います。
　また C99 に対応しているコンパイラなら stdbool.h はありますが未対応なら
　ヘッダはないのでこれまたエラーなります。
　どんなコンパイラを使っているのか分かりませんがこのことを頭の片隅に
　置いておいて下さい。
＞よりメモリを効率よく使いたいため…
　↑
　それなら『ユークリッドの互除法』で計算させる方法もあります。
　http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/ …
　ネットで検索するといろいろ見つかります。
　また『_Bool』型を使ってもメモリ効率が良くなるかは分かりません。
　言語仕様では 0、1 を記憶できれば良いだけで _Bool 型が 1 ビットの領域で
　管理されるかは分かりません。0、1 で管理させたいならビット演算すれば良い。
・下にサンプルを載せます。

サンプル:
// ビット調査
int GetBool( unsigned char bool[], int no )
{
　return (bool[ no >> 3 ] & (1 << (no & 0x7))) ? 1 : 0;
}
// ビット・セット
void SetBool( unsigned char bool[], int no )
{
　bool[ no >> 3 ] |= (1 << (no & 0x7));
}
// ビット・リセット
void ResetBool( unsigned char bool[], int no )
{
　bool[ no >> 3 ] &= ~(1 << (no & 0x7));
}

使い方:
int main( void )
{
　unsigned char BoolTable[ 100 ];　// 800 ビット管理可能
　
　SetBool( BoolTable, 123 );　// 123 番目のビットをON
　
　ResetBool( BoolTable, 456 );　// 456 番目のビットをOFF
　
　if ( GetBool(BoolTable,753) ){　// 753 番目のビットを調査
　　// 753 番目のビットは ON
　}
　else{
　　// 753 番目のビットは OFF
　}
　return 0;
}
以上。

No.1 回答者： asuncion 回答日時： 2007/09/28 21:35

> エラーが出てしまいました。

何をしたときに、どんなエラーが出ましたか？
エラーメッセージの内容を、正確に提示してください。

この回答への補足

インクルードファイル 'stdbool.h' をオープンできない

と出ました。

補足日時：2007/09/28 21:49