素数个数

题目描述

求

输入输出格式

输入格式：

1 个整数

输出格式：

1 个整数，表示素数的个数。

输入输出样例

输入样例#1：

输出样例#1：

说明

• 对于40% 的数据， $10^61≤N≤106；$

• 对于80% 的数据， $10^71≤N≤107；$

• 对于100% 的数据， $10^81≤N≤108。$

$思路$

线性筛的裸板子；

两处优化：

l 去掉所有2的倍数；

l Register修饰符暗示编译程序相应的变量将被频繁地使用，如果可能的话，应将其保存在CPU的寄存器中，以加快其存储速度。

代码

 1 #include<cstdio>
 2 const int maxn=6e6+1;
 3 const int maxm=1e8+1;
 4 int n;
 5 int s[maxn],ss;
 6 bool v[maxm];
 7 int main(){
 8     scanf("%d",&n);
 9     if(n<2){puts("0");return 0;}
10     for(register int i=3;i<=n;i+=2){
11         if(!v[i]) s[ss++]=i;
12          for(register int j=0,k;j<ss;j++){
13              k=i*s[j];
14              if(k>n) break;
15             v[k]=1;
16             if(i%s[j]==0) break;
17          }
18     }
19     printf("%d",ss+1);
20     return 0;
21 }