掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.27474

素数の和
投稿者---わからない(2006/07/03 16:37:37)


例えばキーボードから打ち込んだ数値までの素数の和を求めるプログラムをC言語を使って書きたいのですが、そのアルゴリズムさえどうしたらいいのかわかりません。申し訳ないのですが、誰か簡単に教えて頂けないのでしょうか?まだC言語を初めて1ヶ月なのでよくわかりません。


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:素数の和 27475 Blue 2006/07/03 16:43:21
<子記事> Re:素数の和 27478 shu 2006/07/03 17:55:26
<子記事> Re:素数の和 27479 僕も素人 2006/07/04 10:05:39


No.27475

Re:素数の和
投稿者---Blue(2006/07/03 16:43:21)


素数を列挙する方法はわかりますか?
ここは、数学的な話でC言語が全然わからなくても、大体の手順はわかりますよね?
それをまず、(C言語はまったくかんがえないで)箇条書きしてみてはどうでしょうか?

それから、いままでならったC言語の知識でどのようにすべきかを変換していき、
そこで、ここはどのように記述するんだろうか等、具体的な質問ができたら
再度ここで質問してください。

その際は、
  • 箇条書きにした手順
  • 途中まででいいのでできているソース
  • あなたの環境(OSやコンパイラ)

を明記してください。


この投稿にコメントする

削除パスワード

No.27478

Re:素数の和
投稿者---shu(2006/07/03 17:55:26)


>例えば
なんの例えか良くわからなかった。

>キーボードから打ち込んだ
とりあえず、キーボードからの入力と、素数の和とは関係が無い。
後回し。

>数値までの素数の和を求めるプログラムを
までの前に、からが無い、開始数字は何?、0?

ある数値までのを、只、表示してみる。
ある数値までの和を求めてみる。

素数かどうかの判定は、上の2行のプログラムが書けてから。

>C言語を使って書きたいのですが、
書きたがっていても書けない、
間違っていようが、的外れだろうが、とにかく書く。
1文字、1行でも書く。
コメントでも良い。


この投稿にコメントする

削除パスワード

No.27479

Re:素数の和
投稿者---僕も素人(2006/07/04 10:05:39)


とりあえず数値nが素数かどうか判定するのは、

for(i=2;i<n;i++){
if(n%i==0){
break;  /*素数なので*/
}
}

こういう感じにループするしかないんですかね?
僕はほかに思いつきませんでした。



この投稿にコメントする

削除パスワード

No.27480

Re:素数の和
投稿者---papa(2006/07/04 10:17:50)


>こういう感じにループするしかないんですかね?

1)nが2だったら素数である。
2)nが3以上の奇数で割り切れたら素数ではない。ご提示のような、
iを1ずつカウントアップする方法はあまり効率的ではありません。
3)iの上限値はnの平方根で十分。つまり、i<nのかわりに
i*i<=nでよいはず。

別の方法として、見つかった素数をテーブルに格納しておき、
nが素数テーブルのいずれかの数で割り切れたら素数ではない、
という判定ができると思います。


この投稿にコメントする

削除パスワード

No.27481

Re:素数の和
投稿者---iijima(2006/07/04 10:19:31)


> if(n%i==0){
> break;  /*素数なので*/
> }

そのコメントはどういう意味だろう。
nがiで割り切れたら、nは素数じゃないんでない?



この投稿にコメントする

削除パスワード

No.27482

Re:素数の和
投稿者---僕も素人(2006/07/04 10:26:26)


>i*i<=nでよいはず。
ありがとうございます。ど文系なものでそういう発想が出てきませんでした。
しかし実はなんでそれでよいのか理解したような、してないような...

>nがiで割り切れたら、nは素数じゃないんでない?
すみません。そのとおりです。



この投稿にコメントする

削除パスワード

No.27483

Re:素数の和
投稿者---athos(2006/07/04 11:29:43)


「エラトステネスのふるい」で検索するといいかもしれません。

n以下の全ての素数を求めるのであればこれが単純で効率的なのでは。


この投稿にコメントする

削除パスワード

No.27486

Re:素数の和
投稿者---僕も素人(2006/07/04 13:23:30)


下一桁をまず見て、
偶数だったら素数でない判定。
奇数じゃなかったら調べる。
これは効率的な気がします。


この投稿にコメントする

削除パスワード

No.27487

Re:素数の和
投稿者---papa(2006/07/04 13:34:36)


>奇数じゃなかったら調べる。

ここは、「奇数だったら」が正しいでしょう。
また、for文の中でそもそも奇数だけをチェックするようにしておけば、
「下一桁を見て偶数かどうかを判定する」という必要はありません。



この投稿にコメントする

削除パスワード

No.27489

Re:素数の和
投稿者---僕も素人(2006/07/04 15:56:48)


>また、for文の中でそもそも奇数だけをチェックするようにしておけば、
>「下一桁を見て偶数かどうかを判定する」という必要はありません。

たしかにそうですね。
というより、偶数の場合forの中の最初の計算ではじかれるわけなので、どちらにしろ処理量は変わらないですね。





この投稿にコメントする

削除パスワード

No.27492

Re:素数の和
投稿者---papa(2006/07/04 16:15:28)


>というより、偶数の場合forの中の最初の計算ではじかれるわけなので、どちらにしろ処理量は変わらないですね。

forの中の最初の計算、というのは、例えば
    if ((i % 2) == 0) {
        // 偶数の場合の処理
    }

というような内容を指していますか?
だとすると、「2で割った余りを求めて、0かどうかを判定する」という処理には
けっこうなコスト(処理時間といってもいいと思います)がかかるはずです。

別の内容を指しているのでしたら、すみません。


この投稿にコメントする

削除パスワード

No.27512

Re:素数の和
投稿者---KING・王(2006/07/04 22:50:42)


偶数の判定なら、下記ようにすれば割るよりも処理速度がはやくなるとおもいますが。。。
if( n & 0x01 ){
    /*nが奇数の場合*/
}else{
    /*nが偶数の場合*/
}


また、数値nが奇数と分かっている場合、数値nが素数かどうかの判定のループの中で、
forループの増加量をi++からi+=2に変更した方が効率的では?


この投稿にコメントする

削除パスワード

No.27520

Re:素数の和
投稿者---επιστημη(2006/07/05 07:07:34)


>また、数値nが奇数と分かっている場合、数値nが素数かどうかの判定のループの中で、
>forループの増加量をi++からi+=2に変更した方が効率的では?

2の倍数,3の倍数を最初っから除外するため、
素数の候補を6n±1にするってテもあります。



この投稿にコメントする

削除パスワード

No.27538

Re:素数の和
投稿者---Mook(2006/07/05 15:27:12)
http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9


単純に奇数だけを確認したいなら
    for ( i=3 ; i<=MAX_NUM ; i+=2 ) {
        処理
    }

でよいのでは?

すっかり無視されていますが、エラトステネスのふるいを使用するのが、計算量だけなら一番早いです。
私のPC での測定結果ですが、

エラトステネスのふるい
10000・・・ 0.020 sec
100000・・・ 0.040 sec

全数判定
10000・・・ 0.50 sec
30000・・・ 4.29 sec
50000・・・12.39 sec
100000・・・62.94 sec

といった感じで、最近のPCは高性能なので10000 くらいまでは差が見られませんが、数が大きくなると急速に計算時間がかかってきます。
これは計算量のオーダーが一次と二次の違いです。
オーダーが二次とは、簡単に言えば対象の範囲に対して計算量が二次関数となる、という意味です。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧