问题标题: 酷町堂：6605 酷町猫玩数学游戏

6605   酷町猫玩数学游戏

经验值：1600 时间限制：2000毫秒

题目描述 Description

给定N，求1，2,…,N中素数的个数

输入描述 Input Description

一行：一个整数N

输出描述 Output Description

一行：一个整数表示素数的个数

样例输入 Sample Input

10

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

对于40% 的数据，1≤N≤106
对于 80% 的数据，1≤N≤107
对于 100% 的数据1≤N≤108

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int n,ans,q;
bool b[100000005];
int main(){
    scanf("%d",&n);
    b[1]=true;
    for(int i=2;i<=n;i++){
        if(b[i]==false){
            ans++;
            for(int j=i*2;j<=n;j+=i)
                b[j]=true;
        }
    }
    cout<<ans;
    return 0;
}