AOJ 0009
問題
n 以下の素数の数を数えろ、という内容。
Prime Number
Write a program which reads an integer n (n ≤ 999999) and prints the number of prime numbers which are less than or equal to n. A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. For example, the first four prime numbers are: 2, 3, 5, 7.
Input
Input consists of several datasets. Each dataset has an integer n in a line.
The number of datasets ≤ 30.
Output
For each dataset, prints the number of prime numbers.
Sample Input
10
3
11Output for the Sample Input
4
2
5
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009
解答 (C++)
数えます。
#include<iostream> #include<cmath> using namespace std; int main(){ int n; while(cin >> n){ bool prime[1000000] = {false}; // falseで初期化 prime[1] = true; prime[2] = false; int count = 0; // エラトステネスのふるい for(int j = 2; j * j <= n ; j++){ if(!prime[j]){ for (int k = 2; k*j <= n;k++){ prime[j*k] = true; } } } // falseだと素数 for(int i = 1;i<=n;i++){ if(!prime[i]) count = count +1; } cout << count << endl; } return 0; }
"prime[n] が true だと素数" としたかったのに、false が素数になっています。
bool配列の初期化を{true}にしようとしても、つまり
bool prime[100] = {true}
としたのに prime が all true にならなかった。falseのままだった。
これはダメなんだ。なぜ。分からない。
どうしようもないので false を素数にしました。
解答 (Haskell)
Haskellコードは短くなるので素敵です。
import Control.Applicative main = do n <- read <$> getLine print $ length $ takeWhile (<= n) prime -- 素数のリストからn以下のものを抽出してできるリストの長さ prime :: [Int] prime = [i | i <- [2..], divset i == []] -- 素数のリスト divset :: Int ->[Int] divset n = [j | j <- [2..k], n `mod` j == 0] where k = floor $ sqrt (fromIntegral (n::Int)) -- エラトステネスのふるい
素数のリスト "prime" を作るために約数の集合 "divset" を定義。
takeWhile して長さを調べればOK。Haskellは光。
" import Control.Appricative" は "<$>" を使うためらしいです