#include // time: O(sqrt(n)) .. space: O(1) bool isPrime(int n) { if (n < 2) return false; int iter = 2; while(iter <= sqrt(n)) { if (n % iter == 0) return false; iter++; } return true; }
template bool isPrime(T n) { T i; if(i<2) return false; for(i = 2; i * i <= n; i++) { if(n % i == 0) return false; } return true; }