Prime Number - kyoupuro @ ウィキ

0009 : Prime Number

問題文

解説

入力された整数以下の素数が何個あるかを出力する。
最初にエラトステネスの篩で素数の表を作ればOK。

プログラム

C

C++

...

#include <iostream>
#include <cstdio>
using namespace std;
 
const int MAX = 1000000;
bool prime[MAX] = {false};
 
void set_prime() {
    for (int i = 2; i*i <= MAX; i++) {
        if (prime[i]) continue;
        for (int j = i*2; j <= MAX; j += i) {
            prime[j] = true;
        }
    }
} 
 
int main() {
    set_prime();
     
    int n;
    while (cin >> n) {
        int cnt = 0;
        if (n >= 2) {
            cnt++;
            for (int i = 3; i <= n; i += 2) {
                if (!prime[i]) {
                    cnt++;
               }
            }
        }
        cout << cnt << endl;
    }
     
    return 0;
}

Java