双子の素数

質問

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

回答No.5

betagamma · ベストアンサー

色々間違ってました。正しくは、
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)
でした。

お礼

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

回答No.6

JaritenCat

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

お礼

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

回答No.4

betagamma

エラトステネスのふるいについては、
http://www.hokuriku.ne.jp/fukiyo/math-obe/eratosu.htm
に書いてあります。プログラムでかくなら、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);
}
}

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

お礼

ありがとうございました！！！エラトステネスのふるいについてよく分かりました。本当に感謝しています。
わざわざプログラムリストまで載せて下さって、本当にありがとうございました。

回答No.3

JaritenCat

双子の素数は、３と５、４１と４３みたいに差が２の組（奇数だけ考えたら隣あってる組）ですね。普通に「エラトステネスのふるい」で素数を求めてから双子チェックしたらいいのでは。

お礼

ありがとうございました。

回答No.2

BLUEPIXY

双子の素数ってナンですか？
１７、７１
見たいなものを言うのでしょうか？

補足

No.3の方が回答して下さった通り、ある自然数pとp+2がともに素数であるもののことです。

回答No.1

ceita

http://www.google.com/search?hl=ja&q=%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9&lr=

お礼

素早い回答ありがとうございます。
素数を見つける方法の一つだったんですね。
ありがとうございました。