素数について

質問

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

回答No.7

fatbowler

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です。（この方がベター）

お礼

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

回答No.6

Oh-Orange

★アドバイス
・ちょこっとネット検索したら参考になりそうなページを Wikipedia で見つけました。
　http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A→『素数判定 - 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%E5%88%A4%E5%AE%9A

お礼

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

回答No.5

fatbowler

素数を求めるのは決して難しくないので、ご自分でプログラムを作成されるようお勧めします。
方法は単純で、
・素数かどうか、片っ端からチェックしていく
・チェックの方法は、対象の整数が１以外の数字で割り切れないか、片っ端から試してみる
という力技です。
ヒントとしては、
・偶数は２で割り切れるので、最初から除外してよい
・整数ｎは、√ｎ以下の整数に約数がなければ素数と判断してよい
くらいでしょうか。
頑張って下さい。

補足

今ヒントを元に作ってみたのですが、とても時間がかかり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);
}
}
}
}
}

回答No.4

jacta

> 情けないのですが、素数の求める式が分かりません。もし分かる方がいらっしゃいましたら教えていただけますでしょか。

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

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

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

回答No.3

kaaaiii

概略だけ言いますと、素数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)
～
みたいな感じでやっていけばいいんじゃないでしょうか。
細かいやり方はご自分で考える事をすすめます。

お礼

分かりやすい説明ありがとうございます。
自分なりに改良してみたのですが、なかなか上手くいきません^^;
ありがとうございました。

回答No.2

Werner

たぶん私が下手な説明するよりも、
検索結果見た方が早いと思うので…

素数の求め方 - Google 検索
http://www.google.com/search?hl=ja&lr=lang_ja&ie=UTF-8&oe=UTF-8&q=%E7%B4%A0%E6%95%B0%E3%81%AE%E6%B1%82%E3%82%81%E6%96%B9&num=50
エラトステネスのふるい - Google 検索
http://www.google.com/search?hl=ja&lr=lang_ja&ie=UTF-8&oe=UTF-8&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%E3%81%B5%E3%82%8B%E3%81%84&num=50

お礼

参考にさせていただきました！！
ありがとうございました。

回答No.1

asuncion

手始めに、素数の定義を日本語の文章で書いてみてください。