出産前後の痔にはご注意!

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

このQ&Aに関連する最新のQ&A

A 回答 (6件)

色々間違ってました。

正しくは、
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)
でした。
    • good
    • 0
この回答へのお礼

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

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

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


int isprime[1000];
なので、forでiが1000までまわしちゃうとisprime[1000]にアクセスしてしまうのでまずいのでは?isprimeは[0]から[999]までしかないですよね。
int isprime[1001];
にしましょう。
    • good
    • 0
この回答へのお礼

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

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

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


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);
}
}

}
で行くと思います。未チェックですが。
    • good
    • 0
この回答へのお礼

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

お礼日時:2004/12/06 17:29

双子の素数は、3と5、41と43みたいに差が2の組(奇数だけ考えたら隣あってる組)ですね。

普通に「エラトステネスのふるい」で素数を求めてから双子チェックしたらいいのでは。
    • good
    • 0
この回答へのお礼

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

お礼日時:2004/12/06 17:26

双子の素数ってナンですか?


17、71
見たいなものを言うのでしょうか?

この回答への補足

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

補足日時:2004/12/06 17:23
    • good
    • 0
    • good
    • 0
この回答へのお礼

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

お礼日時:2004/11/14 23:48

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q逆コンパイル、逆アセンブリとは?

逆コンパイル、逆アセンブリとはどういう意味ですか?
教えてください。
よろしくお願いします!

Aベストアンサー

こんばんわ (^^

んーと普通 
プログラムの実行形式はexeファイルでしょ?
それは 元ソースファイルからコンパイルし
それをexe形式にしてるんですよ。

だからvbでつくった環境がなくてもexeにすりゃ
PCにVBがインストールしてなくても実効できるでしょ?
ランタイムは別にして。

ソースコードは一般的に見せません!
オープンソース 非営利ならともかく。
だって 企業秘密ですもん。
見せたら勝手に手加えて 再販売でもされたら
開発した人がかわいそーじゃん。

んで一度exe形式になったらソース原型にはならないよね
そのexeを逆コンパイルし元のソースに戻すことを言います。
イメージ伝わったかしらん?
ではでは。

QC言語初心者の質問失礼いたします。

C言語初心者の質問失礼いたします。
C言語の講義を受けているものなのですが、講義の課題として、

3桁の整数で二乗すると下3桁がもとの数になるものをすべて求めなさい。

というものが出されました。
何をどのようにプログラムすればいいかさえ、まったくわかりません…。
簡単な問題だよと先生は仰っていたのですが、どうにもこうにわからずにいます 涙
どなたか、どうか一言でもかまいませんのでアドバイスいただけませんでしょうか?
よろしくお願いいたします…。

Aベストアンサー

初歩的なアルゴリズムの学習ですね^^

まず、3桁の数字をabcと表すとその二乗は
(a*100 + b*10 +c)^2
=a*a*10000 + 2*a*b*1000 + (2*a*c + b*b)*100 + 2*b*c*10 + c*c
となります。

>3桁の整数で二乗すると下3桁がもとの数になるものをすべて求めなさい。
とのことなので、

(2*a*c + b*b)*100 + 2*b*c*10 + c*c

の部分だけを検討すれば良いことが判ります。

まずcについて式を検討すると、数式から下位一桁は
c*c mod 10 = c
とならなければならないので、cの数値は 0, 1, 5, 6 の4つしか無いことが判ります
またc=0については0になるのは自明なので計算する必要はありません。

次にbについて検討すると
(2*b*c*10 + c*c ) mod 100 = b*10 + c
とならなければなりません。cの値は4つですがc=0は式から、c=1,5,6のみ検討すれば良いことは自明です。またb=0については、c=0になるのが自明ですからこれも計算の必要がありません。

c=1の場合
(20*b + 1) mod 100 = b*10 + 1
2*b mod 10 = b
となり、bは存在しません。従って、最初のcのリストから1を削除します。

c=5の場合
(100*b + 25) mod 100 = b*10 + 5
(10*b + 2) mod 10 = b
b=2となります。

c=6の場合
(120*b + 36) mod 10 = b*10 + 6
12*b + 3 mod 10 = b
b=7となります。

すなわち、下位2桁は25と76のときのみ成立することが判ります。

最後にaを求めますが、a25とa76の18通りの組み合わせを計算すれば良いことになります。
ここから先は課題なので自分で考えてくださいね。

つまりアルゴリズムとしては、1桁めから数字の組み合わせの候補を絞っていけばよいといことです。
以上の考え方でプログラムを組んでみてください。

初歩的なアルゴリズムの学習ですね^^

まず、3桁の数字をabcと表すとその二乗は
(a*100 + b*10 +c)^2
=a*a*10000 + 2*a*b*1000 + (2*a*c + b*b)*100 + 2*b*c*10 + c*c
となります。

>3桁の整数で二乗すると下3桁がもとの数になるものをすべて求めなさい。
とのことなので、

(2*a*c + b*b)*100 + 2*b*c*10 + c*c

の部分だけを検討すれば良いことが判ります。

まずcについて式を検討すると、数式から下位一桁は
c*c mod 10 = c
とならなければならないので、cの数値は 0, 1, 5, 6 の4つしか無いことが判りま...続きを読む

Q○個ずつ改行

C言語を学び始めた初心者です。

エラトステネスのふるいをつかって素数を2から997まで表示するところまで理解できました。
しかし、すべて並べて表示したり、1ずつ改行して表示したりすることはできるのですが、
たとえば10個ずつ改行したいと思った場合どのように変数を設定しループを組み立てればうまくいくでしょうか?

よろしくお願いします

Aベストアンサー

出力した素数の個数を数える変数を用意します。
素数を1個出力したら、個数を1増やします。
個数が10の倍数になったとき、改行コードを出力します。

Qマルコフ連鎖の例を挙げていただけないでしょうか

マルコフ連鎖の理論に関する本を読んだけど、よくわからないんですが、マルコフ連鎖の実際生活用例を挙げていただけないでしょうか。そして、マルコフ連鎖を表現しない用例も挙げて欲しい。

Aベストアンサー

実例としては、次のようなものがあります。

・ATMなどの窓口処理の待ち行列
・遺伝子の塩基配列
・気体・液体などの分子運動
・気象や株、為替、動物の移動など予測が難しいものの動き
ただし、ほんとうはマルコフ連鎖ではないが、予測できないのでマルコフ連鎖で近似しているものがあることに注意してください。

理論としては、次のようなものに応用されています。

・データ圧縮やパターン認識理論
・強化学習
・マルコフ連鎖モンテカルロ法(シミュレーションの一種)
・自動要約・自動作文などの言語処理
・自動作曲
・気象予測モデル
・株や為替などの予測モデル

参考URL
http://tnt.math.se.tmu.ac.jp/labo/grad/2004/masa/graph/7.html
http://www.slideshare.net/teramonagi/ss-5190440
http://itog.sakura.ne.jp/markov/
http://akademeia.info/index.php?%A5%DE%A5%EB%A5%B3%A5%D5%B2%E1%C4%F8

実例としては、次のようなものがあります。

・ATMなどの窓口処理の待ち行列
・遺伝子の塩基配列
・気体・液体などの分子運動
・気象や株、為替、動物の移動など予測が難しいものの動き
ただし、ほんとうはマルコフ連鎖ではないが、予測できないのでマルコフ連鎖で近似しているものがあることに注意してください。

理論としては、次のようなものに応用されています。

・データ圧縮やパターン認識理論
・強化学習
・マルコフ連鎖モンテカルロ法(シミュレーションの一種)
・自動要約・自動作文などの言語処理...続きを読む

Q日付の差分の求め方(日、分)

NT4WS+VC++6.0 Win32コンソールアプリで作ってます。
現在int型で
year1,month1,day1 year2,month2,day2
の様に、1と2それぞれ年月日を持っています。
(year2/month2/day2) - (year1/month1/day1)
と言った感じで1と2の差が何日かを求めたいのです。
VBで言うDateDiffみたいなことがやりたいのです。
よろしくお願いします。

Aベストアンサー

ANSI の範囲で考えると、difftime() という関数が利用できます。difftime() が
扱えるのは time_t 型で表した時刻なのですが、整数で表された年月日などを、この
time_t 型に変換する mktime() という関数と組合わせて使います。

こういうふうに使います。

#include <time.h>
#include <stdio.h>

int main()
{
  int year1, month1, day1;
  int year2, month2, day2;
  year1 = 2001; month1 = 12; day1 = 30;
  year2 = 2002; month2 = 1; day2 = 16;

  {
    struct tm d;
    time_t t1, t2;
    double diff;

    // 開始・終了日を time_t 型の変数にする
    memset(&d, 0, sizeof(d));
    d.tm_year = year1 - 1900;
    d.tm_mon = month1 - 1;
    d.tm_mday = day1;
    t1 = mktime(&d);
    d.tm_year = year2 - 1900;
    d.tm_mon = month2 - 1;
    d.tm_mday = day2;
    t2 = mktime(&d);

    diff = difftime(t2, t1);

    // difftime() の返り値は「秒」で double 型
    // ÷60÷60÷24 で日数にして、+0.5 は四捨五入のため
    printf("%d 日差.\n", (int)(diff / 60 / 60 / 24 + 0.5));
  }

  return 0;
}

ANSI の範囲で考えると、difftime() という関数が利用できます。difftime() が
扱えるのは time_t 型で表した時刻なのですが、整数で表された年月日などを、この
time_t 型に変換する mktime() という関数と組合わせて使います。

こういうふうに使います。

#include <time.h>
#include <stdio.h>

int main()
{
  int year1, month1, day1;
  int year2, month2, day2;
  year1 = 2001; month1 = 12; day1 = 30;
  year2 = 2002; month2 = 1; day2 = 16;

  {
    struct tm d;
...続きを読む

Q因数分解を行うプログラムについて

こんにちは。

今日は教えてほしいことがあってきました。
学校の課題で

a,b,cは整数で、しかもaは0でないものとして、
このとき2次式
   ax^2 + bx + c
を、整数係数の範囲で因数分解するプログラムを作る

ことになったのですが、

1.任意のa,b,cの値を入れてもらう。

2.二次方程式の解で
  整数係数の範囲で因数分解できるか判別する。

3.なにかを用いて分解する。

4.結果を表示する。
  (dX + e)(fX + g)のような形で。

とまでは考えられるのですが、
3.の所が難しくて、考えてからかなり時間がたってしまい
らちがあかない感じです。
たすきがけを使うにしても、いまいち、よくわかりません。

どなたか、教えてください。お願いします。

Aベストアンサー

No.3 ですが、計算部分を省略せずに書きます。

x = (-b ± √(b^2 - 4ac)) / 2a
この式をこれ変形させる必要はありません。

実際に、3x^2 + 14x + 8 を順に計算してみます。
a = 3
b = 14
c = 8
このa, b, cの値を代入するわけだから、

x = (-14 ± √(14^2 - 4×3×8)) / 2×3
x = (-14 ± √100) / 6
ここで、±を2つに分けて、
x = (-14 + 10) / 6, x = (-14 - 10) / 6
x = -4 / 6, x = -24 / 6
x = -2/3, x = -4

プログラムとして考えていくと、√(b^2 - 4ac) から考えて、
int q = (b * b - 4 * a * c); // q = 100
int r = sqrt(q); // r = 10
if (r * r != q) { // sqrt の結果が整数でなければ解なし
return 解なし;
}

この後、割り算を計算せずに、分数として別の変数に持ちます。
int n1 = -b + r; // +の分子 (n1 = -4)
int m1 = 2 * a; // 分母 (m1 = 6)

この時点で、(6x + 4) と表示させる事もできますが、なんらかの方法で n1/m1 を約分することで、(3x + 2) と表示させる事は難しくないと思います。

同様に、
int n2 = -b - r; // -の分子 (n2 = -24)
int m2 = 2 * a; // 分母 (m2 = 6)
これも、-24/6 を -4/1 に約分することで (x + 4) と表示できるでしょう。

ここで符号について考えてみると、(3x + 2)(x + 4) の符号を全て反転させて、(-3x - 2)(-x - 4) としたとしても全く同じですが、あえて2つ表示する必要はないのではないかと思います。

No.3 ですが、計算部分を省略せずに書きます。

x = (-b ± √(b^2 - 4ac)) / 2a
この式をこれ変形させる必要はありません。

実際に、3x^2 + 14x + 8 を順に計算してみます。
a = 3
b = 14
c = 8
このa, b, cの値を代入するわけだから、

x = (-14 ± √(14^2 - 4×3×8)) / 2×3
x = (-14 ± √100) / 6
ここで、±を2つに分けて、
x = (-14 + 10) / 6, x = (-14 - 10) / 6
x = -4 / 6, x = -24 / 6
x = -2/3, x = -4

プログラムとして考えていくと、√(b^2 - 4ac) から考えて、
int q = (b * b - 4 *...続きを読む

QC言語<素数を求めるプログラム>

#include<stdio.h>
int j;
int prime(int n)
{
int i;

if(n < 2) return 0;
if(n == 2) return 1;
if(n%2 == 0) return 0;

for(i = 3; i*i<= n; i += 2){
if(n%i == 0) return 0;
}
return 1;
}

int main(void)
{
int n;

for(n=1; n <= 1000; n++)
{
if(prime(n)){

printf("%d\n",n);
j++;
}
}
printf("素数の個数は全部で %d 件見つかりました。\n",j);

return 0;
}

このプログラムは1から1000までの素数のみを表示させるプログラムでありますが、このアルゴリズムが全くわかりません。
int prime(int n)の中身のアルゴリズムがどういう仕組みになっているのかお分かりになりますでしょうか?

#include<stdio.h>
int j;
int prime(int n)
{
int i;

if(n < 2) return 0;
if(n == 2) return 1;
if(n%2 == 0) return 0;

for(i = 3; i*i<= n; i += 2){
if(n%i == 0) return 0;
}
return 1;
}

int main(void)
{
int n;

for(n=1; n <= 1000; n++)
{
if(prime(n)){

printf("%d\n",n);
j++;
}
}
printf("素数の個数は全部で %d 件見つかりました。\n",j);

return 0;
}

このプログラムは1から1000までの素数のみを表示させるプログラムであり...続きを読む

Aベストアンサー

「int prime(int n)」内についてですが、
if(n < 2) return 0;
 →2未満の数字は素数としない、つまり「1」の時は素数ではないと判断したい処理ですね
if(n == 2) return 1;
 →2の時は無条件に素数と判断する為です
if(n%2 == 0) return 0;
 →nを2で割った時のあまりが0だったら素数ではない、つまり(2より大きい)偶数の時は絶対素数ではないので偶数をはぶく為の処理ですね
for(i = 3; i*i<= n; i += 2){
if(n%i == 0) return 0;
}
 →割る数(i)を3から5、7、9・・・のように増やしていって、nを割ったときのあまりが0かどうか判断しています。
  例:n=9場合、i=3の時に9/3であまりが0になるので、9は3で割り切れるから9は素数じゃない!
  の処理をしています。
return 1;
 →で、最後のreturnですが、これは説明不要でしょか?
  ここに来るまで素数じゃないと判断されたらreturn 0で途中で処理を抜けています。
  つまりここまで来たら素数なのでreturn 1を返します。

で、よろしいでしょうか?

「int prime(int n)」内についてですが、
if(n < 2) return 0;
 →2未満の数字は素数としない、つまり「1」の時は素数ではないと判断したい処理ですね
if(n == 2) return 1;
 →2の時は無条件に素数と判断する為です
if(n%2 == 0) return 0;
 →nを2で割った時のあまりが0だったら素数ではない、つまり(2より大きい)偶数の時は絶対素数ではないので偶数をはぶく為の処理ですね
for(i = 3; i*i<= n; i += 2){
if(n%i == 0) return 0;
}
 →割る数(i)を3から5、7、9・・・のように増やし...続きを読む

Q秒数を入力すると○時間○分○秒と計算するプログラム

はじめまして、Javaのプログラムの問題で
プログラム実行後に秒数を入力すると○時間○分○秒と計算するプログラムを作成しろとでました。
例 何秒を変換しますか?
  3856(キーボードから入力)
  3856秒は1時間4分16秒です。

for文を使うらしいのですが調べても全く分からない状態です。
学校でJavaを習ってまだ半年です。教科書はやさしいJava第3版です。
回答のほうお願いいたします。

Aベストアンサー

Javaだと課題の丸投げになっちゃいますから、C言語で回答してみる。

#include "stdio.h"

int main(void)
{
int s,s2,m,h;

printf("何秒を変換しますか?:");
scanf("%d", &s);

m = s / 60;
s2 = s % 60;

h = m / 60;
m = m % 60;

printf("%dは%d時間%d分%d秒です。\n",s,h,m,s2);
}


人気Q&Aランキング