```
class Solution {
public:
int countPrimes(int n) {
int primes[1000000];
int size=1;
if(n<=2) return 0;
primes[0]=2;
for(int i=3;i<n;i++){
bool isPrime=true;
for(int j=0;j<size&&primes[j]*primes[j]<=i;j++){
if(i%primes[j]==0){
isPrime=false;
break;
}
}
if(isPrime){
primes[size]=i;
size++;
}
}
return size;
}
};
```

This code AC but if I use primes as a vector, TLE with input n=1500000;