1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
|
#define ull unsigned long long #define ll long long #define inf 0x3f3f3f3f #define mod (int)1e9+7 #define for0(i, n) for (int i = 0; i < n; i++) #define for1(i, n) for (int i = 1; i <= n; i++) #define forl(i, l, r) for (int i = l; i <= r; i++) #define forn(i, n) for (int i = n; i >= 0; i--) #define mem0(a) memset(a, 0, sizeof(a)) #define mem1(a) memset(a, 1 , sizeof(a)) #define mem_1(a) memset(a, -1, sizeof(a)) #define meminf(a) memset(a, inf, sizeof(a)) using namespace std;
const int N=100005; bool a[N+1]; vector<int> prime; void (){ memset(a,true,sizeof(a)); for(int i=2;i<=N;i++){ if(a[i]) prime.push_back(i); for(int j=0;j<(int)prime.size()&&i*prime[j]<=N;j++){ a[i*prime[j]]=false; if(!(i%prime[j])) break; } } } int main(){ ll t,a,b; bool isprime[100005]; getPrime(); cin>>t; for1(k,t){ int ans=0; cin>>a>>b; mem1(isprime); for(int i=0;prime[i]*prime[i]<=b&&i<(int)prime.size();i++){ ll l=a/prime[i]; if (l*prime[i]<a) l++; if (l<2) l=2; for (; l*prime[i]<=b; l++) isprime[l*prime[i]-a]=0; } if (a==1) isprime[0]=0; for0(i,b-a+1) if (isprime[i])ans++; printf("Case %d: %dn",k,ans ); } return 0; }
|
近期评论