vector<int> prime ={2,3,5,7,11};
// for( int k=2;k<=sqrt(n);k++)
for(int k=0;k<prime.size();k++)
if(prime[k] > sqrt(n)) break;
if(n%prime[k] ==0) return false;
if(n<=prime[prime.size()-1])
for(int i=0;i<prime.size();i++)
if(n<=prime[i]) return i;
for(int k = prime[prime.size()-1]+2 ; k<n; k+=2)
if( isPrime(k)) prime.push_back(k);