40026118素数的个数

试题描述

给定整数 n ，请你统计不超 n 的素数的个数。

输入

仅包含一个正整数 n 。

输出

不超过 n 的素数的个数。

输入示例

11

输出示例

5

其他说明

数据范围：1 <= n <= 10^6 。

样例说明：有 2、3、5、7、11 共 5 个素数。

1 #include
       
         2 #define LL long long 3 #define maxn 1000010 4 using namespace std; 5 LL read() 6 { 7     LL x=0,f=1; 8     char c=getchar(); 9     while(!isdigit(c)){
     if(c=='-')f=-1;c=getchar();}10     while(isdigit(c)){x=x*10+c-'0';c=getchar();}11     return x*f;12 }13 bool prime[maxn];14 LL a;15 void prime_table()16 {17     for(int i=2;(LL)i<=a;i++) prime[i]=1;18     for(int i=2;(LL)i*i<=a;i++)19         if(prime[i]) for(LL j=i*i;j<=a;j+=i) prime[j]=0;20     return;21 }22 23 int main()24 {25     a=read();26     prime_table();27     int cnt=0;28     for(int i=2;i<=a;i++)if(prime[i]) cnt++;29     printf("%d\n", cnt);30     system("pause");31     return 0;32 }