Try: Pollard's rho

check the number by each prime number less than 10^4 till it get it smallest prime factor which are around 1200 so it can be done. if prime number less than 10^4 is not factor so it is clear that n have all prime factor greater than 10^4 therefore n can have maximum two no. of factor than there are only three possibility that either

1- Number is itself is prime number so it can be check using Miller Rabin algorithm in O(k(logn)^3)

2- Number is square of prime number so again it can be check

3- Number is product of two distinct prime number. Using Pollard Rho Algorithm we can find the factor of number and smallest number will be smallest prime factor of number in O(n^1/4)

It will be done in O(10^3) Hope it Help!! Sorry for bad English !!

Store the primes less than 10^6 and factorise by iterating over primes less than sqrt(N). Complexity will be around sqrt(N)/logN.