C言語関係掲示板

過去ログ

No714 自然数nまでの素数

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

素数
投稿者---あやや(2003/07/23 01:54:12)


自然数nを入力したらnまでの素数を表示させるプログラムを教えてください!!
Linuxです。

No.8585

Re:素数
投稿者---物見遊山(2003/07/23 12:27:25)


>自然数nを入力したらnまでの素数を表示させるプログラムを教えてください!!

「エラトステネスの篩い」を調べましょう。

>Linuxです。

あー。そうですか。

No.8602

Re:素数
投稿者---かずま(2003/07/24 02:29:08)


> 「エラトステネスの篩い」を調べましょう。

やっぱり、掛け算も割り算も使わないから、かなり高速ですね。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
    int n, m, i, j;  char *p;

    if (scanf("%d", &n) == 1)
        if (m = sqrt(n), p = calloc(1, n+1))
            for (i = 2; i <= n; i++)
                if (p[i] == 0)
                    if (printf("%d\n", i), i <= m)
                        for (j = i+i; j <= n; j += i)
                            p[j] = 1;
    return 0;
}


No.8621

Re:素数
投稿者---かずま(2003/07/24 20:13:57)


> やっぱり、掛け算も割り算も使わないから、かなり高速ですね。
でも、掛け算を使って、

    for (j = i+i; j <= n; j += i)
を
    for (j = i*i; j <= n; j += i)

に変えたほうがきっと速くなるでしょう。

それから、sqrt のような浮動小数点演算をなくしたければ、
m = sqrt(n), を削除し、i <= m を i*i <= n に変えれば
よいでしょう。速くなるかどうかは何とも言えません。


No.8630

Re:素数
投稿者---かずま(2003/07/25 00:02:06)


> それから、sqrt のような浮動小数点の演算をしたくなければ、
> m = sqrt(n), を削除し、i &lt;= m を i*i &lt;= n に変えれば
> よいでしょう。速くなるかどうかは何とも言えません。

やっぱり、これはだめです。

n = 1000000 の場合、i = 46337 という素数が求まるところまでは
いいんですが、次の素数である i = 46349 のとき、i * i が int の
最大値を超えてしまい、負の値となってしまいますね。いい忘れました
が、n = 1000000 ですから、int が 4バイトの処理系を仮定しています。

No.8638

Re:素数
投稿者---物見遊山(2003/07/25 12:25:21)


兄さんが答えてどーするんすか。

それはさておき。

かずまさんの独特?なスタイルと精緻な考え方は
小ネタ(=学ぶべきところ)が満載で
いつも勉強させてもらってます。

なんか絞まりの悪い終わり方。
ファンレターというモノだな。

No.8586

Re:素数
投稿者---かずま(2003/07/23 16:06:43)


> 自然数nを入力したらnまでの素数を表示させるプログラムを教えてください!!
    if (scanf("%d", &n) == 1 && n > 1)
        for (i = 2; i <= n; i++ == j && printf("%d\n", j))
            for (j = 2; i % j; j++)
                ;

こんな馬鹿プログラムだと、昔は n = 10000 でもしんどかったのに、
最近の PC は速くて(2.8GHz)、n = 100000 でも大丈夫みたいですね。

No.8588

Re:素数
投稿者---ROM(2003/07/23 17:48:16)


どうすればもっと速くできるんだろう。
私の頭じゃこれが精一杯。

#include <stdio.h>

typedef unsigned long ulong;

ulong table[7000];
ulong *end = table;

ulong square_root(ulong x)  /* アルゴリズム辞典丸写し^^; */
{
    ulong s, t;
    if (x == 0)
        return 0;
    s = 1;
    t = x;
    while (s < t) {
        s <<= 1;
        t >>= 1;
    }
    do {
        t = s;
        s = (x / s + s) >> 1;
    } while (s < t);
    return t;
}

void init_prime_number(void)
{
    table[0] = ~0UL;
}

int is_prime_number(ulong n)
{
    ulong *p;
    ulong root;
    if (n < 2)
        return 0;
    root = square_root(n);
    for (p = table; *p <= root; p++) {
        if (n % *p == 0)
            return 0;
    }
    if (n < 65536)
        *end++ = n;
    return 1;
}

void main(void)
{
    ulong n, i, f;

    init_prime_number();

    printf("n = ");
    scanf("%ld", &n);

    f = 0;
    for (i = 0; i <= n; i++) {
        if (is_prime_number(i)) {
            f++;
            printf("%ld ", i);
        }
    }
    printf("\nf = %ld\n", f);
}


No.8589

Re:素数
投稿者---たいちう(2003/07/23 19:37:22)


>どうすればもっと速くできるんだろう。

mainのforですが、2以外の偶数を調べる必要はないでしょう。
これで多分少しだけ速くなる。

No.8597

Re:素数
投稿者---aki(2003/07/23 22:11:03)


#include <stdio.h>

enum {max = 1000000};

/* 素数を与えると、その素数より大きい最小の素数を返す */
int next_prime(int n)
{
    static int next_p[max+1];
    int i, p = n;

    if (n == 2)
        n = 3;
    else
NEXT:    for (n += 2, i = 3; i * i <= n; i = next_p[i])
            if (n % i == 0) goto NEXT;
    return next_p[p] = n;
}

int main(void)
{
    int i, n;

    while (printf("max? "), scanf("%d", &n) == 1) {
        if (n < 2 || max < n) continue;
        for (i = 2; i <= n; i = next_prime(i))
            printf("%d\t", i);
        putchar('\n');
    }
    return 0;
}


No.8633

Re:素数
投稿者---あやや(2003/07/25 09:14:50)


みなさんありがとうございます。
だけど、私には全く理解不能です。
もっと、基本的(簡単)な内容のものをお願いします。
わがまま言ってすいませんm(__)m

No.8636

Re:素数
投稿者---かずま(2003/07/25 10:49:39)


> だけど、私には全く理解不能です。
> もっと、基本的(簡単)な内容のものをお願いします。

では、あなたのレベルに合った説明をしましょう。
そのためにはあなたのレベルを知らなければなりません。
次の質問に答えてください。

1. 自然数 n を入力したら n を表示させるプログラムを書けますか。書いてください。
2. 自然数 n を入力したら 1 から n までを表示させるプログラムを書けますか。
3. 自然数 n を入力したら n までの奇数を表示させるプログラムを書けますか。
4. n が 100 のとき、どんな表示がされることを期待しているのかを書いてください。
 プログラムではなく、自分で求めた結果で結構です。
5. 4 の結果はどういうやりかたで求めたのかを説明してください。

No.8637

Re:素数
投稿者---かずま(2003/07/25 11:00:07)


> 4. n が 100 のとき、どんな表示がされることを期待しているのかを書いてください。
>  プログラムではなく、自分で求めた結果で結構です。

補足します。
これは、3 のプログラムではなく、「自然数nを入力したらnまでの素数を
表示させるプログラム」についての話です。

No.8642

Re:素数
投稿者---masayan(2003/07/25 16:02:38)


いきなり飛び込みですいません。私はもっとレベルが低いので
この問題ができるかちょっとやってみました。一応実行してできたんですけど
もしなんか違ってたら教えてください。
>1. 自然数 n を入力したら n を表示させるプログラムを書けますか。書いてください。
#include <stdio.h>
main()
{
	int a;

	printf("data= ");
	scanf("%d", &a);

	printf("data = %d\n",a);
}

>2. 自然数 n を入力したら 1 から n までを表示させるプログラムを書けますか。
#include <stdio.h>
main()
{
	int a = 0;
	int i;

	printf("data= ");
	scanf("%d", &a);

	printf("data = %d\n",a);

	for(i=0; i<=a; i++) {
		printf("%d.", i);
	}
}

>3. 自然数 n を入力したら n までの奇数を表示させるプログラムを書けますか。
#include <stdio.h>

main()
{
	int a = 0;
	int i;

	printf("data= ");
	scanf("%d", &a);

	printf("data = %d\n",a);

	for(i=0; i<=a; i++) {
		if(i%2 == 1) {
			printf("%d\n",i);
		}
	}
}

>4. n が 100 のとき、どんな表示がされることを期待しているのかを書いてください。
> プログラムではなく、自分で求めた結果で結構です。
>5. 4 の結果はどういうやりかたで求めたのかを説明してください。
4の素数の表示は今考えています。

No.8653

Re:素数
投稿者---あやや(2003/07/26 14:02:20)


知っているのは
int
scanf
printf
if
char
while
for
float
配列
です。

No.8654

Re:素数
投稿者---あかま(2003/07/26 18:01:17)


それだけ知っていれば、かずまさんの1〜5の質問にすべて答えられます。
masayanさんがソースを示していますが、それを見ないで質問に答えられることをおすすめします。
でないとほんとにあなたレベルに合わせてプログラムを作ることなんて出来ません。

まぁ、かずまさんが最初にしめした
    if (scanf("%d", &n) == 1 && n > 1)
        for (i = 2; i <= n; i++ == j && printf("%d\n", j))
            for (j = 2; i % j; j++)
                ;


このプログラムが一番簡単だと思いますが。

No.8674

Re:素数
投稿者---ゆうた(2003/07/29 15:59:29)


自分もあややさんとおなじ課題取り組んでて悩んでいます。
かずまさんが示された
<pre> if (scanf("%d", &n) == 1 && n > 1)
for (i = 2; i <= n; i++ == j && printf("%d\n", j))
for (j = 2; i % j; j++)
;

</pre>
このプログラムの全体教えていただけませんか?
お願いしますm(_ _)m
 

No.8679

Re:素数
投稿者---かずま(2003/07/29 19:33:31)


> 自分もあややさんとおなじ課題取り組んでて悩んでいます。

http://www.geisya.or.jp/~mwm48961/math/m3prime2.htm

ここに書かれていることは理解していますか?

No.8724

Re:素数
投稿者---ゆうた(2003/07/31 12:25:51)



> http://www.geisya.or.jp/~mwm48961/math/m3prime2.htm
>
>ここに書かれていることは理解していますか?

そこにかかれていることはわかります。けれどc言語で書くときわからなくて・・。


No.8678

Re:素数
投稿者---かずま(2003/07/29 19:06:35)


>    if (scanf("%d", &n) == 1 && n > 1)
>        for (i = 2; i <= n; i++ == j && printf("%d\n", j))
>            for (j = 2; i % j; j++)
>                ;
>
> このプログラムが一番簡単だと思いますが。
 
そのプログラムは、ちょっとふざけて書いてあるのでよくありません。
次のように書き換えます。

    if (scanf("%d", &n) != 1) return 1;
    for (i = 2; i <= n; i++) {
        for (j = 2; i % j != 0; j++)
            ;
        if (j == i)
            printf("%d\n", i);
    }


No.8732

Re:素数
投稿者---ゆうた(2003/07/31 13:37:48)


お答えありがとうございます。
自分には「!」の意味がわからなかったのですが、
それを使わずなんとか完成しました。
これです↓
#include <stdio.h>

void main(void)
{
int i, j, n;

printf("数字を入力してください。");
scanf("%d",&j);
printf("それまでの素数を表示します\n");
for(n = 2; n <= j; n++)
{
for(i = 2; i <= n-1; i++)
if(n%i == 0)
break;
if (i > n-1)
printf("%d\n",n);
 }
}


No.8685

Re:素数
投稿者---あかま(2003/07/30 13:46:15)


なんとなく勝手に採点してみる。
>1. 自然数 n を入力したら n を表示させるプログラムを書けますか。書いてください。
#include <stdio.h>
main()
{
	int a;

	printf("data= ");
	scanf("%d", &a);

	printf("data = %d\n",a);
}

100点。

>2. 自然数 n を入力したら 1 から n までを表示させるプログラムを書けますか。
#include <stdio.h>
main()
{
	int a = 0;
	int i;

	printf("data= ");
	scanf("%d", &a);

	printf("data = %d\n",a);

	for(i=0; i<=a; i++) {
		printf("%d.", i);
	}
}

99点。0から表示してるよ(笑)

>3. 自然数 n を入力したら n までの奇数を表示させるプログラムを書けますか。
#include <stdio.h>

main()
{
	int a = 0;
	int i;

	printf("data= ");
	scanf("%d", &a);

	printf("data = %d\n",a);

	for(i=0; i<=a; i++) {
		if(i%2 == 1) {
			printf("%d\n",i);
		}
	}
}

%を使ってるあたり技術的には100点。
でも奇数を表示させるだけなら
for(i=1; i<=a; i+=2) {

でよかったりする。


No.8747

Re:素数
投稿者---masayan(2003/08/01 09:56:05)


なるほど。参考になります。
採点ありがとうございました。