1453 统计素数个数 2

 

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 黄金 Gold

 

 

 

题目描述

Description

判断[a,b]中素数的个数

输入描述

Input Description

输入共1行,a,b两数

输出描述

Output Description

输出共1行,输出素数的个数

样例输入

Sample Input

3 5

样例输出

Sample Output

2

数据范围及提示

Data Size & Hint

对于100%的数据,a,b≤5000,000

1 #include
          
            2 #include
           
             3 #include
            
              4 using namespace std; 5 const int N=5000000; 6 int vis[N]; 7 int main() 8 { 9     int l,r;10     cin>>l>>r;11     vis[0]=1;12     vis[1]=1;13     for(int i=2;i<=sqrt(r)+1;i++)14      {15          if(vis[i]==0)16           {17               for(int j=i*2;j<=r;j+=i)18                {19                    vis[j]=1;20                 } 21           }22      }23      int ans=0;24      for(int i=l;i<=r;i++)25       {26           if(vis[i]==0)27            {28                ans++;29            }30       }31       cout<