1 #pragma GCC optimize(2) 2 #include <bits/stdc++.h> 3 using namespace std; 4 bool isprime[1000000010]; 5 vector<int> prime; 6 inline int getlist(int n,int m){ 7 isprime[1]=1; 8 int ans=0; 9 for(int i=2;i<=m;i++){ 10 if(!isprime[i]){ 11 prime.push_back(i); 12 } 13 if(!(i^(n-1))){ 14 ans=prime.size(); 15 } 16 for(int j=0;j<prime.size()&&i*prime[j]<=m;j++){ 17 isprime[i*prime[j]]=1; 18 if(!(i%prime[j])){ 19 break; 20 } 21 } 22 } 23 return ans; 24 } 25 int main(){ 26 int m,n; 27 cin>>n>>m; 28 int ans=getlist(n,m); 29 int ans1=prime.size(); 30 cout<<ans1-ans<<endl; 31 system("pause"); 32 return 0; 33 }
是目前網上極快的版本
采用歐拉篩.
由于用了STL所以建議吸氧
可以直接使用,由于我太蒻了,有不好的請直說
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/251.html
標籤：C++