时间复杂度<O(N*N),线性筛法

#include<bits/stdc++.h>
using namespace std;
int f[10005],p[10005],cnt,n,m,ans;
void prime(int n){
	f[1]=1;
	for(int i=2;i<=n;i++){
		if(f[i]==0) p[++cnt]=i;
		for(int j=1;j<=cnt;j++){
			if(i*p[j]>n) break;
			f[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
}
int main(){
	cin>>n>>m;
	prime(m);
	for(int i=n;i<=m;i++){
		if(f[i]==0) ans++;
	}
	cout<<ans;
	return 0;
}
//O(n)