Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define inf 2e18
- int MOD=1000000007;//998244353;
- const int n=1000050;
- bool prime[n]; //array to store precalculated primes till 10^6
- void cal_primes(){memset(prime,true,sizeof(prime)); for(int i=2;i<=sqrt(n);++i){ if(prime[i]==true){ for(int j=i*i;j<=n;j+=i){prime[j]=false;}}}}
- bool check(int i)
- {
- while(i>0)
- {
- if(i==1)
- return true;
- if(i%5==0)
- i/=5;
- else if(i%3==0)
- i/=3;
- else
- return false;
- }
- }
- void solve(int t)
- {
- int testcases=t;
- while(t--)
- {
- int l,r,c=0;
- cin>>l>>r;
- vector<bool>p(n+1,false);
- vector<int>cnt(n+1,0);
- for(int i=0;i<n;i++){
- if(check(i))
- p[i]=true;
- }
- for(int i=1;i<n;i++){
- if(p[i]==true){
- ++c;
- }
- cnt[i]=c;
- }
- int ans;
- if(l==0)
- ans=cnt[r];
- else
- ans=(cnt[r]-cnt[l-1]);
- cout<<ans<<endl;
- }
- }
- main()
- {
- auto start=chrono::system_clock::now();
- {
- ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- int t=1;
- // cin>>t;
- solve(t);
- }
- auto end=chrono::system_clock::now();
- chrono::duration<double> elapsed=end-start;
- // cout<<endl<<"Time taken: "<<elapsed.count()<<" sec";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement