Basically I am storing all primes upto sqrt(10**9).
Now For checking a number as primes, I check if it is divisible by any of the primes upto srt(of that number).
Please tell me how to find the time complexity of such code.
Here is my code:-
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MX 31622
#define endl "\n"
vector<int> primes;
void init(){
vector<bool> sieve(MX+1,true);
sieve[0] = sieve[1] =false;
for(int i=2;i<=MX;i++){
if(sieve[i]){
primes.push_back(i);
for(int j=i*i;j<=MX;j+=i){
sieve[j] = false;
}
}
}
}
inline bool check(int num){
int n = (int)sqrt(num);
for(int i=0;i<primes.size() && primes[i]<=n;i++){
if(num%primes[i] == 0){
return false;
}
}
return true;
}
void solve(int l, int r){
for(int i=max(l,2);i<=r;i++){
if(check(i))
cout<<i<<endl;
}
}
int main() {
init();
int n;
cin>>n;
while(n--){
int l,r;
cin>>l>>r;
solve(l,r);
cout<<endl;
}
return 0;
}