TLE Not So Easy Math

#1

#include
using namespace std;
int main() {
unsigned long long int t;
cin>>t;
unsigned long long int n;
while(t–){
cin>>n;
unsigned long long int cnt=0;
for(unsigned long long int i=1;i<=n;i=i+2){
if(i%3==0 || i%5==0 || i%7==0 || i%11==0 || i%13==0 || i%17==0 || i%19==0 ){
cnt++;
}
}
cout<<((n/2)+cnt)<<endl;
}
return 0;
}

TLE for 1 test case. How to optimise the code?

#2

You cannot write a for loop since n<=10^18.Try storing all the prime numbers from 1 to 20 in an array and use this array of prime numbers to calculate the numbers that can be divided by them using recursion.(and since the size of this array is very small so you can apply recursion ).