とある高専生の割と誰得なウェブページです。
Prime Number
6 桁以下の正の整数 n を入力し、n 以下の素数がいくつあるかを出力するプログラムを作成して下さい。ただし、素数とは 1 と自分自身でしか割り切れない正の整数のうち 1 をのぞいたものをいいます。例えば 10 以下の素数は、2, 3, 5, 7 です。
Input
複数のデータセットが与えられます。各データセットに n が１行に与えられます。入力の最後まで処理して下さい。
Output
各データセットごとに、n 以下の素数の個数を１行に出力して下さい。
Sample Input
10Output for the Sample Input
4
「エラトステネスの篩」を用いて 1 から 999999 までの整数について素数かどうかを bool 型配列 t に格納 (素数なら false ，素数でないなら true ) し，配列のはじめから n 番目の要素までに素数がいくつあるかカウントした。
#include <iostream>
using namespace std;
bool t[999999] = {false};
int main()
{
int n, c, i, j;
t[0] = true;
for (i = 2; i * i <= 999999; i++)
{
if (!t[i-1])
{
for (j = i+i; j <= 999999; j+=i)
t[j-1] = true;
}
}
while (cin >> n)
{
if (cin.eof()) break;
for (i = c = 0; i < n; i++)
if (!t[i]) c++;
cout << c << endl;
}
}