We know that any natural number $n$ can be decomposed as $p_1^{k_1}p_2^{k_2}...p_n^{k_n}$. I am looking for numbers which have $k_1=k_2=k_3=....=k_n=1$ i.e. given a number n, identify if it has all the $k_i=1$. I am looking for fast solutions, heuristics are welcome. One can assume that primes upto $n$ are stored.
Edit: $p_1, p_2, ....p_n$ are any primes and not necessarily the first n primes.
You are looking for squarefree numbers. Unfortunately, as pointed out in the comments, no test faster than factoring has been developed to determine whether a number is squarefree.