双子の素数

解決済

質問者：candlize
質問日時：2004/11/14 01:53
回答数：6件

3～1000の範囲で双子の素数をすべて求めるプログラムの作り方を教えて下さい。友人には「『エラトステネスのふるい』を使え」と言われたのですが、「エラトステネスのふるい」とは一体何なのでしょうか？それも教えて頂きたいです。

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (6件)

ベストアンサー優先
最新から表示
回答順に表示

No.5ベストアンサー

回答者： betagamma
回答日時：2004/11/14 04:37

色々間違ってました。

正しくは、
int main(void){
int i,j;
int isprime[1000];
//最初はすべての数が素数だと思う
for(i=0;i<=1000;i++){
isprime[i]=1;
}
//誤動作しないようにする。
isprime[0]=isprime[1]=0;
//2からはじめる
for(i=2;i<=1000;i++){
if(isprime[i]==1){
for(j=2*i;j<=1000;j+=i){
isprime[j]=0;
}
}
}

//双子素数をプリントする
for(i=2;i<=1000;i++){
if(isprime[i-2]==1 && isprime[i]==1){
print("(%d,%d)",i-2,i);
}
}

}
で、結果は、
(3,5)(5,7)(11,13)(17,19)(29,31)(41,43)(59,61)(71,73)(101,103)(107,109)(137,139)(149,151)(179,181)(191,193)(197,199)(227,229)(239,241)(269,271)(281,283)(311,313)
(347,349)(419,421)(431,433)(461,463)(521,523)(569,571)(599,601)(617,619)(641,643)(659,661)(809,811)(821,823)(827,829)(857,859)(881,883)
でした。

- 0
- 件

通報する

この回答へのお礼

お礼がとても遅れてしまい、本当に申し訳ありません。
プログラムリストを載せて頂いた上訂正までして頂いて、本当にありがとうございました。
遅ればせながら、良回答にさせていただきます。

通報する

お礼日時：2005/01/28 23:06

No.6

回答者： JaritenCat
回答日時：2004/11/14 04:48

No.5のプログラムですが、

int isprime[1000];
なので、forでiが1000までまわしちゃうとisprime[1000]にアクセスしてしまうのでまずいのでは？isprimeは[0]から[999]までしかないですよね。
int isprime[1001];
にしましょう。

- 0
- 件

通報する

この回答へのお礼

お礼がとても遅れてしまい、本当に申し訳ありません。
良いアドバイスをありがとうございました。

通報する

お礼日時：2005/01/28 23:09

No.4

回答者： betagamma
回答日時：2004/11/14 04:30

エラトステネスのふるいについては、

http://www.hokuriku.ne.jp/fukiyo/math-obe/eratos …
に書いてあります。プログラムでかくなら、1000個の配列を作って、
#include <stdio.h>

int main(void){

int isprime[1000];
//最初はすべての数が素数だと思う
for(i=0;i<=1000;i++){
isprime[i]=1;
}
//誤動作しないようにする。
isprime[0]=isprime[1]=0;
//2からはじめる
for(i=2;i<=1000;i++){
if(isprime[i]==1){
for(j=i;j<=1000;j+=i){
isprime[j]=0;
}
}
}

//双子素数をプリントする
for(i=2;i<=1000;i++){
if(isprime[i-2]==1 && isprime[i]==1){
print("(%d,%d)",i-2,i);
}
}

}
で行くと思います。未チェックですが。