求[l, r]这段区间中有多少素数
1 ≤ l ≤ r ≤ 10
一个显然的想法是利用for循环枚举[l, r]中的每一个数。然后利用朴素算法O(√X)进行判断。
整体复杂度O(N√N),不符合要求
#include<iostream> using namespace std; int r,l; int ans; int main(){ cin>>r>>l; for( int i=r ; i<=l ; ++i ){ if( n%i!=0 ){ ans++; } } cout<<ans; return 0; }
仍然考虑枚举判断每个数是否是素数，但我们这次从2开始判断。
考虑对于任意一个数x,不论x是否为素数，都有x*2,x*3,x*4...为合数。我们“筛”掉这些必然为合数的数。那么当我们枚举到i，i还没有被筛掉，那么i必然为素数。
时间复杂度O(NlogN)
#include<iostream> using namespace std; int r,l; int prime[1e6],c; bool num[1e6]; int ans; int main(){ cin>>r>>l; for( int i=2 ; i<=l ; ++i ){ if( !num[i] ) prime[++c]=i; if( i>=r && i<=l && !num[i] ) ans++; for( int j=1 ; i*prime[j]<=n && j<=c ; ++j ){ num[ i*prime[j] ] = 1; if( i%prime[j]==0 ) break; } } cout<<ans; return 0; }
原文：https://www.cnblogs.com/morui/p/10786123.html