C言語関係掲示板

過去ログ

No.441.最初から数えてx番目の素数

[戻る] [ホームページ]
No.3115

お願いします。
投稿者---J(2002/10/24 16:46:29)


最初から数えてx番目の素数を求めるのは、どうすればよいのでしょうか?

No.3126

Re:お願いします。
投稿者---かずま(2002/10/24 22:17:27)


> 最初から数えてx番目の素数を求めるのは、どうすればよいのでしょうか?
#include <stdio.h>

int main()
{
    int x, i, j, k;

    while (printf("何番目? "), scanf("%d", &x) == 1) {
        k = 0;
        for (i = 2; ; i++) {
            for (j = 2; i % j; j++)
                ;
            if (i == j && ++k == x)
                break;
        }
        printf("%d\n", i);
    }
    return 0;
}

1000番目ぐらいまでで良ければ、これで十分でしょう。
1 と自分以外で割り切れないという素数の定義どおりですから。

No.3159

Re:お願いします。
投稿者---J(2002/10/26 17:04:51)


>> 最初から数えてx番目の素数を求めるのは、どうすればよいのでしょうか?
><pre>
#include <stdio.h>

int main()
{
int x, i, j, k;

while (printf("何番目? "), scanf("%d", &x) == 1) {
k = 0;
for (i = 2; ; i++) {
for (j = 2; i % j; j++)
;
if (i == j && ++k == x)
break;
}
printf("%d\n", i);
}
return 0;
}
</pre>
>1000番目ぐらいまでで良ければ、これで十分でしょう。
>1 と自分以外で割り切れないという素数の定義どおりですから。


Jです。コンパイルできないのですがどうしてですか?


No.3163

Re:お願いします。
投稿者---PSB(2002/10/26 22:23:10)


>Jです。コンパイルできないのですがどうしてですか?

普通にコンパイルできますけど?


No.3184

Re:お願いします。
投稿者---J(2002/10/28 16:01:06)


>>Jです。コンパイルできないのですがどうしてですか?
>
>普通にコンパイルできますけど?

すいません。できました。ききたいんですけど、whileのとこにある
==1は、どういうことですか。何番目をnとおいて n= x*1というふうにし、何番目かをもとめたいけど、どうすればいいですか。


No.3192

Re:お願いします。
投稿者---PSB(2002/10/28 23:14:41)


>==1は、どういうことですか。

1と同値。

>何番目をnとおいて n= x*1というふうにし、何番目かをもとめたいけど、どうすればいいですか。

???




No.3195

プログラムの流れがわかりません。
投稿者---J(2002/10/29 10:41:53)


>>==1は、どういうことですか。
>
>1と同値。
>
>>何番目をnとおいて n= x*1というふうにし、何番目かをもとめたいけど、どうすればいいですか。
>
>???
>
>
ようするに、式を使い何番目かを求め表示したいのです。あと2番目のforのところの i%j はどういうことですか。あそこは、条件式がはいるところではないのですか?もう一つ、プログラムの流れがよくわかりません。例としてscanfで5を入力したときどうなるかおしえてください。


No.3202

Re:プログラムの流れがわかりません。
投稿者---すず(2002/10/29 13:43:04)


お久しぶりです。すずです。
Jさん、はじめまして。

>ようするに、式を使い何番目かを求め表示したいのです。

かずまさんのプログラムでは、入力した値xが、Jさんが求めたいnにあたります。
そして、iが素数にあたります。これでわかりましたか??

>あと2番目のforのところの i%j はどういうことですか。
>あそこは、条件式がはいるところではないのですか?

i%jは剰余を求める演算子です。
つまり、5/2=2…1、の1を求めるものです。

では、こちらからJさんに質問です。
Jさんのおっしゃる”条件”とは如何なるものを指しているのでしょうか??
かずまさんのプログラムは、0でない間ループするという、”継続条件”です。

>例としてscanfで5を入力したときどうなるかおしえてください。

それは、ご自分でステップ実行をしたらいかがでしょうか?

No.3233

ありがとうごさいます。
投稿者---J(2002/10/30 09:54:41)



>それは、ご自分でステップ実行をしたらいかがでしょうか?


ありがとうごさいます。<や<=などがないので、どうしてかなと思いまして。そういう条件になるのですね。こんど桁を増やして、1万番目までもとめたいです。かずまさんのプログラムを変えたらできますか?


No.3238

Re:ありがとうごさいます。
投稿者---かずま(2002/10/30 11:20:40)


> こんど桁を増やして、1万番目までもとめたいです。
> かずまさんのプログラムを変えたらできますか?

できますが、その前に、
・元のプログラムを完全に理解されていますか?
・なぜ、1万番目を求めることが出来ないか分かりますか?
・それ以前に、素数とは何かを理解されていますか?
以上、ぜびお答えください。

修正方法は、
for (j = 2; i % j; j++) を for (j = 2; j*j <= i && i % j; j++) に
if (i == j && ++k == x) を if (j*j > i && ++k == x) に変えるだけです。

結果が大きくなるので、int が 32ビットのコンパイラを使ってください。

No.3246

Re:ありがとうごさいます。Jです。
投稿者---J(2002/10/30 16:59:11)


>・元のプログラムを完全に理解されていますか?
>・なぜ、1万番目を求めることが出来ないか分かりますか?
>・それ以前に、素数とは何かを理解されていますか?
>以上、ぜびお答えください。

完全に理解していません。1000のときと10000のときのプログラムを見比べても、なぜ、10000まで表示出来ないかわかりません。よろしかったら、くわしく教えて下さい。お願いします。
素数については、これくらい知っています。『素数の定義は「1とその数自身以外では割り切れない自然数」で、tがsqrt(t)以下の全ての素数で割り切れないとき、tは素数。』


No.3237

Re:プログラムの流れがわかりません。
投稿者---TDa(2002/10/30 11:10:00)



>ようするに、式を使い何番目かを求め表示したいのです。あと2番目のforのところの i%j はどういうことですか。あそこは、条件式がはいるところではないのですか?

よく誤解している人がいるのですがforの書式は
for (式; 式; 式) 文 です。
条件式というのは文法上はありません。よって式なら何でもかけます。



No.3239

Re:プログラムの流れがわかりません。
投稿者---かずま(2002/10/30 11:32:59)


> よく誤解している人がいるのですがforの書式は
> for (式; 式; 式) 文 です。
> 条件式というのは文法上はありません。よって式なら何でもかけます。

「for (式; 式; 式) 文 です。よって式なら何でもかけます。」は、その通り。
しかし、「条件式というのは文法上はありません」は、間違いです。

conditional-expression:
  logical-OR-expression
  logical-OR-expression ? expression : conditional-expression

ですから、条件式(conditional expression) は文法(syntax)上あります。
規格では、条件演算子 ? : を使う式のことを条件式といいます。

No.3240

Re:プログラムの流れがわかりません。
投稿者---TDa(2002/10/30 12:27:56)



>規格では、条件演算子 ? : を使う式のことを条件式といいます。

リファレンスを調べないで書き込みました。訂正ありがとうございます。