C言語で、次のプログラムを作ってみて頂けないでしょうか？

「キーボードから２以上の整数を入力して、
素数であるかどうか判断をする」

というプログラムをCで作るにはどうしたらいいですか？

できたら、見本のプログラムを示して頂けると
一番助かります。

よろしくお願いします。

No.1 回答者： arukamun 回答日時： 2003/07/06 01:15

こんばんは

とりあえず見本ですね。
エラトステネスのふるいでいいでしょう。

#include <stdio.h>

#define PRIME 1
#define NOTPRIME 0

int prime(int p)
{
　　int i ;

　　if ( p < 2 || n%2 == 0 ){
　　　　return NOTPRIME ;
　　}
　　for (i=3 ;i*i<=p ;i+=2){
　　　　if ( p%i == 0 ){
　　　　　　return NOTPRIME ;
　　　　}
　　}
　　return PRIME ;
}

void main()
{
　　int p ;

　　printf("２以上の整数を入力してください : ");
　　scanf("%d",&p);
　　if ( prime(p) == PRIME ){
　　　　printf("%dは素数です。",p);
　　} else {
　　　　printf("%dは素数ではありません。",p);
　　}
}

No.2 回答者： coolguys 回答日時： 2003/07/06 01:26

＃１の人の答えは宿題等である場合は、

使わないほうが吉です。

初心者の作ったものと違いますから、
見る人が見たら、他人が作ったことが分かってしまいますよ。

この回答への補足

宿題等ではありませんが、

参考書の参考問題にあったので、聞いてみたのです。
その参考書には問題の解答もありましたが、それは理解ができなかったので、ほかのプログラムを聞いているのです。

補足日時：2003/07/06 23:26

No.3 回答者： Jitta 回答日時： 2003/07/06 23:23

こんにちは。

　答え。作れません。なぜなら、入力できる数の下限はありますが、上限がないからです。たとえば、9京なんて数字を入力されると、コンピュータは別の数字として扱い、答えが信用できません。


　まぁ、学校の授業で出るような問題でこんな答えをしたら×ですが、実務で作るプログラムでは、こういうことを考えないといけません。

この回答への補足

宿題等ではありませんが、

参考書の参考問題にあったので、聞いてみたのです。
その参考書には問題の解答もありましたが、それは理解ができなかったので、ほかのプログラムを聞いているのです。

ですから、できないことはないかと思われます。

補足日時：2003/07/06 23:25

No.4 回答者： arukamun 回答日時： 2003/07/07 00:26

こんばんは、No.1のarukamunです。

入力ミスです。（腕が落ちたなぁ。）

誤　　if ( p < 2 || n%2 == 0 ){
nなんて変数は定義して無いし、
p = 2の時、素数では無くなってしまいますね。

正　　if ( p < 2 || ( p > 2 && p%2 == 0 ) ){

ところで、No.1のプログラムは理解出来ましたか？

prime()という関数の引数にint型の数値を入れると、素数かを判断し、0(NOTPRIME)か1(PRIME)を返します。
int型を超える数値を入れると正しく動作しない事はNo.3の方が仰る通りですね。まあ、サンプルですので、バグが有っても構わないでしょう。

まずは、
　　if ( p < 2 || ( p > 2 && p%2 == 0 ) ){
　　　　return NOTPRIME ;
　　}
で、pが２より小さい、または、２より大きくて２で割った時に余りが０であったら素数では無い。としています。
次に
　　for (i=3 ;i*i<=p ;i+=2){
　　　　if ( p%i == 0 ){
　　　　　　return NOTPRIME ;
　　　　}
　　}
で、i=3で３で割った時の余りが０であったら素数では無い。
５で割った時の余りが０であったら素数では無い。
・・・
の様に、i+=2で２ずつ加算して検査しています。
ループの終了条件が、i*i<=pというのは、出来るだけ計算回数を少なくしたかったからです。
なぜ、i*i<=pで良いかは考えてください。
別にi<pでもi<p/2でも良いですけど・・・。

解らない所が有れば、補足してください。

No.5 回答者： bikkuri 回答日時： 2003/07/07 11:52

>問題の解答もありましたが、それは理解ができなかったので

とありましたが、具体的に何が書いてあってなにが理解できなかったかを
明記すると、適切な回答が得られる可能性が高まりますよ。

ちょっと考えるだけでも
１．解答にプログラム例があったが、その内容がわからない。
２．解答に解説があったが、実際のプログラムのイメージにならない。
３．解答のプログラム／解説のアルゴリズム（判断方法）がわからない。
くらい可能性があるでしょう。

最初の質問の「見本のプログラムが欲しい」から推測すると
２番に近いとは思うが、ずばりでもないような。

以下は、私なりの見本
int i, input;
char *msg;
scanf("%d", &input);
msg = "素数です";
for(i=2; i<input; i++) {
・・if(input % i == 0) {
・・・・msg = "素数じゃない";
・・・・break;
・・}
}
printf("%s\n", msg);

処理内容は、素数の定義そのもの（１とそれ自身以外では割り切れない）
でテストしています。
（もっとも単純だが、無駄も多い）