素数について

締切済

質問者：gether
質問日時：2007/06/29 23:18
回答数：7件

1000000以下の素数を求め画面に表示するプログラムを作りなさい。
結果をファイルに出力し（sosuu.dat）、
レポートはソースプログラムとsosuu.datの両方を添付してください。
という課題が出ました。

情けないのですが、素数の求める式が分かりません。もし分かる方がいらっしゃいましたら教えていただけますでしょか。お願いします。
以下のプログラムは今回の関連授業で作ったものです。以下のプログラムで使った文字だけで、今回のプログラムを作れますでしょうか。お願いします。

友愛数を求めるプログラムその２
#include "stdio.h"
void main ()
{
unsigned long int a, b, c, i;
FILE *fp;
fp = fopen ("yuuai.dat", "w");
for (i = 2; i < 3000000L; i++)
{
a = 1;
b = 2;
while (b <= i / b)
{
if (i % b == 0)
{
if (b != i / b)
{
a += b + i / b;
}
else
{
a += b;
}
}
b++;
}
if (a > i)
{
b = 2;
c = 1;
while (b <= a / b)
{
if (a % b == 0)
{
if (b != a / b)
{
c += b + a / b;
}
else
{
c += b;
}
}
b++;
}
if (c == i)
{
printf ("%d %dYn", i, a);
fprintf (fp, "%d %dYn", i, a);
}
}
}
fclose (fp);
}

通報する

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

質問の本文を隠す

回答 (7件)

最新から表示
回答順に表示

No.7

回答者： fatbowler
回答日時：2007/07/01 06:45

ANo.5の補足に対して。

「とても時間がかかり100までの素数を出すのも難しいです。」
とは、計算に時間がかかるのではなくて、割り切れるものがあるかどうか試すのに、
片っ端からif文を書いていくのに時間がかかる、という意味ですよね？
割られる数も取り違えているようです。
d=sqrt(i);
はあくまで終了条件で、

iが3で割り切れない
iが5で割り切れない
iが7で割り切れない
　　・
　　・
　　・
iがdで割り切れない
が全て成り立てば、iは素数である

が私のアドバイスの内容です。（奇数が偶数で割り切れるはずがないので偶数は省略）
そのままコーディングしたのが下記になります。
全角スペースは半角スペースに置き換えて下さい。
（全角スペースでインデントするのが見やすそうですね。）

--------
#include "stdio.h"
#include "math.h"
void main ()
{
　　　　int i,j,d,sflg;
　　　　printf("2\n");
　　　　for (i = 3; i <= 1000000; i+=2)
　　　　{
　　　　　　　　d = (int)sqrt(i);
　　　　　　　　sflg = 1;
　　　　　　　　for(j = 3; j <= d; j++)
　　　　　　　　{
　　　　　　　　　　　　if(i%j == 0)
　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　sflg = 0;
　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　}
　　　　　　　　}
　　　　　　　　if(sflg)
　　　　　　　　{
　　　　　　　　　　　　printf("%d\n",i);
　　　　　　　　}
　　　　}
}

--------
なお、質問者のコードを重視して
　　　　d = (int)sqrt(i);
　　　　for(j = 3; j <= d; j++)
と、sqrt()をそのまま使いましたが()、この計算には時間が掛かりますのでANo.6のように、
　　　　for(j = 3; (j*J) <= i; j++)
とした方がベターです。
もっとも、今回は私の環境では体感的に差は出ませんでしたが。

あと、sosuu.dat の方は大丈夫ですか？
Windowsならコマンドプロンプトで画面への出力をファイルに落ちるようにリダイレクトするだけですが。
ファイルをfopenして、printfをfprintfに置き換えてもOKです。（この方がベター）

- 0
- 件

通報する

この回答へのお礼

本当にありがとうございました。
fatbowlerさんのプログラムを殆ど使わせていただきました。
sosuu.datも上手くできました。
忙しい中、たくさんの力を貸してくださり本当にありがとうございました。

通報する

お礼日時：2007/07/01 12:27

No.6

回答者： Oh-Orange
回答日時：2007/06/30 14:30

★アドバイス

・ちょこっとネット検索したら参考になりそうなページを Wikipedia で見つけました。
　http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0% …→『素数判定 - Wikipedia』
　これを参考に素数一覧のソースを作って見ました。

サンプル:
// 素数判定
int IsPrime( int n )
{
　int i;
　
　if ( n　< 2 ) return 0;
　if ( n == 2 ) return 1;
　if ( !(n % 2) ) return 0;
　
　for ( i = 3 ; (i * i) <= n ; i += 2 ){
　　if ( !(n % i) ){
　　　return 0;
　　}
　}
　return 1;
}

// 素数一覧
int main( void )
{
　int i;
　
　printf( "<< 素数一覧 >>\n" );
　for ( i = 1 ; i <= 1000000 ; i++ ){
　　if ( IsPrime(i) ){
　　　printf( "%d ", i );
　　}
　}
　printf( "\n" );
　return 0;
}

その他:
・私の環境ではリダイレクションしてファイルに保存すると 1～2 秒で終了しました。
　あと『友愛数』を求められるのなら素数も出来そうな気はしますが…。
・以上。

参考URL：http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0% …

- 0
- 件

通報する

この回答へのお礼

プログラムまで作ってくださり、ありがとうございました。
友愛数は授業でヒントをたくさん得ながらだったので作れたのですが、自力では素数にも手も足も出せない状態でした。
本当にありがとうございました。

通報する

お礼日時：2007/07/01 12:29

No.5

回答者： fatbowler
回答日時：2007/06/30 09:27

素数を求めるのは決して難しくないので、ご自分でプログラムを作成されるようお勧めします。

方法は単純で、
・素数かどうか、片っ端からチェックしていく
・チェックの方法は、対象の整数が１以外の数字で割り切れないか、片っ端から試してみる
という力技です。
ヒントとしては、
・偶数は２で割り切れるので、最初から除外してよい
・整数ｎは、√ｎ以下の整数に約数がなければ素数と判断してよい
くらいでしょうか。
頑張って下さい。

この回答への補足

今ヒントを元に作ってみたのですが、とても時間がかかり100までの素数を出すのも難しいです。どうすればよいでしょうか？
#include "stdio.h"
#include "math.h"
void main ()
{
int i,d;
printf("2\n");
printf("3\n");
printf("5\n");
printf("7\n");
for (i = 8; i <= 100; i++)
{
d=sqrt(i);
while (d % 2 != 0)
{
if(d%3!=0)
{
if(d%5!=0)
{
if(d%7!=0)
printf("%d\n",i);
}
}
}
}
}

補足日時：2007/06/30 10:21

通報する

- 0
- 件

通報する

No.4

回答者： jacta
回答日時：2007/06/30 00:23

> 情けないのですが、素数の求める式が分かりません。

もし分かる方がいらっしゃいましたら教えていただけますでしょか。

必ず結果が素数となる公式を見つけることは多くの数学者の夢です。

> 以下のプログラムは今回の関連授業で作ったものです。以下のプログラムで使った文字だけで、今回のプログラムを作れますでしょうか。

作れます。
/や%のような演算子になる文字も含まれていますし、必要なキーワードや関数を構成する文字も含まれているようです。

- 0
- 件

通報する

No.3

回答者： kaaaiii
回答日時：2007/06/29 23:43

概略だけ言いますと、素数iは i>=n*n (n>=2)までの間に、nで割れない数、です。

例えば19は、19>=4*4までに、2,3,4で割れません。
5*5だと19を超えちゃいますよね。だから素数です。

つまりこのプログラムの作り方は、
for (i = 2; i <= 1000000; i++)
{
n=2;
while (i >= n*n) {
if (i % n == 0)
～
みたいな感じでやっていけばいいんじゃないでしょうか。
細かいやり方はご自分で考える事をすすめます。