// TODO:
// for n \le 10^6, O(1)
// by precomputing 10^6 prime numbers,
// for n \le 10^12, O(\sqrt{N})
// try dividing by prime numbers less than sqrt(n).
// actually, number of prime numbers is abount 82000. (\le 10^6)
// for n \le 10^18, miller rabin.