ページ

2012/05/30

[競技プログラミング][C言語][AOJ0009]Prime Number

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp

Prime Number

6 桁以下の正の整数 n を入力し、n 以下の素数がいくつあるかを出力するプログラムを作成して下さい。
ただし、素数とは 1 と自分自身でしか割り切れない正の整数のうち 1 をのぞいたものをいいます。
例えば 10 以下の素数は、2, 3, 5, 7 です。

Input

複数のデータセットが与えられます。各データセットに n が1行に与えられます。入力の最後まで処理して下さい。

Output

各データセットごとに、n 以下の素数の個数を1行に出力して下さい。
回答:AOJ/vol0/AOJ0009.cpp at master · wada811/AOJ
与えられた整数まで自前で素数判定してカウントすると頑張って高速化しても通らない悲劇…。
どうやら素数判定にはエラストテネスのふるいというものを使うらしい。
これを知らずに自力で頑張って上手くいかなくて半日潰れて泣いた。素数もうやだ…。
そしてこれからのAOJの問題が知ってるかどうかになってきたので萎えてきた。
いい加減C言語でやり続けるのも辛いし、
AOJをひたすら解き続けるのも面白くないのでココで一旦AOJは止めます。

同じ競技プログラミングのAtCoderは2週間に一回くらいなので続けるつもり。
言語は多分C言語ではなくなると思う。
Javascriptを学びたいけど直近の課題としてPHPがあるのでPHPでゴニョゴニョしてるかも。