【モリタポ有償】C/C++の問題を片付けます(2)

516 ： ◆6W4srb4nmo ：2011/04/25(月) 11:58:02.46

[1] 授業数学の問題をC言語で解く
[2] 問題
整数xを0から100000までの整数として,xが３つの素数の和で表現できるなら
その三素数を出力するプログラムを作成せよ。立方数が最大の組合せを出力せよ。
[3.1] 7
[3.2] gcc
[3.3] C
[4] 期限：25日9:00
[5] その他制限：純粋Cライブラリ。

517 ：デフォルトの名無しさん：2011/04/25(月) 12:39:03.51

>>513
> ・一問あたり 500円（5000モリタポ・手数料込み）です。

518 ：デフォルトの名無しさん：2011/04/25(月) 12:40:08.09

お試し期間中ということなので
どんなコードが返ってくるか楽しみです。

[1] 問題
素数41は6つの連続する素数の和として表せる:　41 = 2 + 3 + 5 + 7 + 11 + 13.
100未満の素数を連続する素数の和で表したときにこれが最長になる.
同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ.
100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?

[2] 環境
　[2.1] OS： Windows|Linux
　[2.2] コンパイラ名とバージョン： gcc 4.5
　[2.3] 言語： C
[3] 回答希望期限：なし
[4] その他の制限：標準ライブラリのみ使用可。なるべく速いコードでお願いします。

519 ：デフォルトの名無しさん：2011/04/25(月) 13:35:01.16

5秒くらいかかっちゃうな

520 ：デフォルトの名無しさん：2011/04/25(月) 13:38:29.60

>>518
これって核になるアルゴリズム見つかってんのかな？
和を構成する組み合わせが計算量爆発に見えるんだが…。

521 ：デフォルトの名無しさん：2011/04/25(月) 13:40:03.03

あ、あらゆる素数の組み合わせじゃなくて「連続する素数の和」か。

522 ：デフォルトの名無しさん：2011/04/25(月) 13:57:21.97

1秒未満にできた

523 ：デフォルトの名無しさん：2011/04/25(月) 14:33:36.76

1000000000
21.203 sec

100000000
2.093 sec

10000000
0.234 sec

1000000
0.031 sec

524 ：デフォルトの名無しさん：2011/04/25(月) 15:16:55.39

>>519
１００万迄の素数を作った後で、
１００万から初めて、大きいほうから小さいほうへ順に素数を調べるんですか？

525 ：デフォルトの名無しさん：2011/04/25(月) 15:21:02.65

最大は997651で543個か。
ちょっと書いてみたが実行に五分くらいかかったｗ
ノーセンス＼(^o^)／ｵﾜﾀ

526 ：524：2011/04/25(月) 15:46:43.30

536 個 :2 +..+ 3863 = 958577
よりは大きそうだ。ノーセンス

527 ：デフォルトの名無しさん：2011/04/25(月) 15:53:33.96

997651 543個
995111 1587個
99819619 4685個
999715711 13935個

タイムは>>523よりちょっといいけど、マシンスペックの差かな

528 ：デフォルトの名無しさん：2011/04/25(月) 16:59:39.09

あれ？ここまで◆QZaw55cn4cの書き込みが無いって事は、ひょっとして
>>516のプログラムが書けないのかな？

529 ：デフォルトの名無しさん：2011/04/25(月) 20:46:56.33

おまえらが言い出さないから俺が言ってやる。
なにかこう、胸の奥がチクッとしないか。
小さい時に弟を泣かせたときのような、
なんかそういう気分しないか。俺はする。

530 ：デフォルトの名無しさん：2011/04/25(月) 20:52:11.98

>>529
俺の弟は可愛かったけどね
◆QZaw55cn4cは天の邪鬼だからいじめたくなる

531 ：デフォルトの名無しさん：2011/04/25(月) 20:55:46.16

仮に弟だったとしても公共の場で好き勝手してたら、殴る

532 ：デフォルトの名無しさん：2011/04/25(月) 20:57:31.82

ま、この機会に◆QZaw55cn4cは人から嫌われるとどうなるか
骨の髄まで味わうといいね

533 ：デフォルトの名無しさん：2011/04/25(月) 21:01:05.70

constのつけかたも逆に覚えてるような子をいぢめてはいけない。
たぶん、我々が思う以上に彼は背伸びしてたのかもしれないね。

534 ： ◆QZaw55cn4c ：2011/04/25(月) 21:03:10.67

>>516
http://codepad.org/XNlfz5lK
http://hibari.2ch.net/test/read.cgi/tech/1301553333/439 の指摘を受けて細かいところを変更しました。
＞素数の調べ方がクソ
エラトステネスのふるいは必要なメモリ容量が半端でないので、「クソ」かもしれませんが、素朴な方法にしました。10万までなら、（私の環境では）十分な速度が出ています。
しかし、割り算を二回実行してしまうのはなんとかしたいと思いつつも改良できないでいます。
＞ループにも無駄が多すぎ
ちょっとだけましになったと思います。

535 ：デフォルトの名無しさん：2011/04/25(月) 21:04:12.33

>>533
>たぶん、我々が思う以上に彼は背伸びしてたのかもしれないね。

そんな事はかなり前から分かっていたよ
でもどんなに指摘しても屁理屈で返して来るからとうとう切れたね

536 ： ◆QZaw55cn4c ：2011/04/25(月) 21:05:10.42

>>528
今から取りかかります。しばしお待ちを。

537 ：デフォルトの名無しさん：2011/04/25(月) 21:12:51.34

しかしC言語で書くと二分木扱うだけでプログラムの半分以上さいちゃうのか
言語指定がCだから仕方が無いけど、車輪の再発明って大変ですね

538 ：デフォルトの名無しさん：2011/04/25(月) 21:48:28.19

2chで金儲けっていいの？

539 ：デフォルトの名無しさん：2011/04/25(月) 22:16:04.06

>>534
篩よりよっぽど多量のメモリを使っておきながら、なに寝言ほざいちゃってんの？

540 ： ◆QZaw55cn4c ：2011/04/25(月) 22:33:46.27

>>518
http://codepad.org/leLh4OPx
ごくありきたりな内容になりました。工夫したのは二分探索と計算打ち切りのタイミングでしょうか。
PenIII 866 で 3秒くらいです。

codepad の方がはやいとは。

541 ： ◆QZaw55cn4c ：2011/04/25(月) 22:45:16.42

>>539
ビット演算はできれば避けたいのが本音です。

542 ：デフォルトの名無しさん：2011/04/25(月) 22:49:38.52

ビット関係なくムダに使ってるけどｗ

543 ： ◆QZaw55cn4c ：2011/04/25(月) 22:55:02.33

>>542
ん？なにが無駄ですか？

544 ：デフォルトの名無しさん：2011/04/25(月) 22:59:54.91

>#define N 100000
>#define TABSIZE 10000
>static int primeS[N];

こんなムダに気づかない人間がよく平気な顔して生きてられるな

545 ：デフォルトの名無しさん：2011/04/25(月) 23:05:58.68

>>544
微々たるものだし、質問者本人も
なるべく速いコードでお願いします。
という希望だから
その絡みはさすがに無理があると思う

546 ：デフォルトの名無しさん：2011/04/25(月) 23:13:27.95

◆QZaw55cn4cを外して他人のフリするのやめろよｗ

547 ：デフォルトの名無しさん：2011/04/25(月) 23:15:19.79

マジキチか

548 ：デフォルトの名無しさん：2011/04/25(月) 23:15:54.81

>>545
何を指摘しているか理解できたら、微々たる物なんて言えないけど

549 ： ◆QZaw55cn4c ：2011/04/25(月) 23:17:37.82

>>544
ご指摘感謝いたします。たしかに無駄、あるいはバグでした。
>>516
http://codepad.org/rUHBx91i
>>518
http://codepad.org/XoEg5qnr
>>545
どうもです。

550 ：デフォルトの名無しさん：2011/04/25(月) 23:30:18.69

>>548
何を指してるの？
メモリ使用量、速度ともに認識不能レベルだと思うけどねぇ

551 ：デフォルトの名無しさん：2011/04/25(月) 23:34:25.52

10倍のメモリ使用量が認識できない人がいたｗ

552 ：デフォルトの名無しさん：2011/04/25(月) 23:38:16.91

だから擁護は◆QZaw55cn4cだと何度言えば

553 ：デフォルトの名無しさん：2011/04/25(月) 23:41:27.01

こんな稚拙なコードで金取ろうなんて厚かましいにもほどがある。

554 ：デフォルトの名無しさん：2011/04/25(月) 23:47:29.80

>>551
KB単位のメモリ使用量とか
マイクロ秒単位の速度向上なんて
認識出来んわ

555 ：デフォルトの名無しさん：2011/04/25(月) 23:50:46.13

学生さんなのかな

556 ：デフォルトの名無しさん：2011/04/25(月) 23:52:59.86

>>555
中年ニートだと
人生オワットルわ

557 ：デフォルトの名無しさん：2011/04/25(月) 23:58:35.80

実測してもクソ遅いし、見ただけでもムダが多いコードに何言ってんだｗ

558 ：デフォルトの名無しさん：2011/04/26(火) 13:47:07.22

立方数が最大のものだけ出力すればいいのに

559 ： ◆QZaw55cn4c ：2011/04/26(火) 19:17:43.86

>>557
ご指摘ありがとうございます。たしかにまだまだ改良の余地はありました。とりあえず、>>518 の foundp() を取り入れました。
Knuth だったか、最初の思いつきはベストの思いつきではない、というわけでした。
>>516
http://codepad.org/aSa5w9AE

でも、ここまで来て、私以外にコードを晒す人はいないようですね。

560 ：デフォルトの名無しさん：2011/04/26(火) 19:22:04.71

>>559
>でも、ここまで来て、私以外にコードを晒す人はいないようですね。

それが何か？嫌だったら無理に晒さなくてもいいんだよｗ

561 ：デフォルトの名無しさん：2011/04/26(火) 19:36:49.63

>>559
お前みたいなカスに参考にされるのがイヤだから

562 ： ◆QZaw55cn4c ：2011/04/26(火) 19:43:32.80

>>560
GPL/コピーレフトの思想から考えても、ソースコードを晒すことからすべてが始まると思いますけれどもね。
コードを晒すことなしにどうこういわれても、それは砂上の空論でしょうね。
>>561
多分、参考にもならないから、ご懸念なさっている心配はないと思いますよ :-)

563 ：デフォルトの名無しさん：2011/04/26(火) 19:51:09.06

◆QZaw55cn4cがいるために、他の方が勉強の機会を奪われてしまうのは残念ですね。

564 ：デフォルトの名無しさん：2011/04/26(火) 19:51:12.60

>>559のアホなところもまだまだ指摘できるし、>>518に関しても10倍以上速いコード書けるけどなｗ

565 ：デフォルトの名無しさん：2011/04/26(火) 19:57:16.75

>>564
実力を見せ付けてやれ