素数个数

题目描述
求 1,2,.....,N 中素数的个数。
输入输出格式
输入格式：
1 个整数 N。
输出格式：
1 个整数，表示素数的个数。
输入输出样例
输入样例#1： 
10
输出样例#1： 
4
说明
• 对于40% 的数据， 1≤N≤10^6
• 对于80% 的数据， 1≤N≤10^7
• 对于100% 的数据，1≤N≤10^8

题面

一看到题面，我们肯定会想到线性筛

但是普通线性筛的写法对于本题不适用

我们可以借鉴他的思想

要求的是素数，那就把合数筛掉

令ans=n-1(1既非合数，又非素数)

假设i是质数,那么j*i(j=1,2,3......)一定是合数

筛到j*i时,ans--即可

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<cstdio>
 6 #include<cmath> 
 7 #define ll long long
 8 #define DB double
 9 using namespace std;
10 inline int read()
11 {
12     int x=0,w=1;char ch=getchar();
13     while(!isdigit(ch)){if(ch=='-') w=-1;ch=getchar();}
14     while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
15     return x*w;
16 }
17 int n,ans;
18 bool v[100000001];
19 int main()
20 {
21     n=read();
22     int ans=n-1;
23     for(int i=2;i*i<=n;++i)
24     {
25         if(v[i]) continue;
26         for(int j=2;j*i<=n;++j)
27          if(v[i*j]==0) v[i*j]=1,ans--;
28     }
29     cout<<ans;
30     return 0;
31 }

View Code