300億円欲しい

メジャーリーグのデータ解析します

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
11

Output 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" は "<$>" を使うためらしいです