INPUT: an integer $n$ and a integer $d$
QUESTION: does $n$ have a prime factor less than $d$?
Does a polynomial time algorithm exist that can tell whether or not $n$ has a prime factor $< d$?
Would iterating through all possible primes $< d$ take too long?
Iterating through all possible primes $\lt d$ would in fact take too long; assuming that $n$ and $d$ are both given in binary and that $d$ is comparable to $n$, then it would take time exponential in the size of your input. But you don't have to iterate through all possible primes; instead, you can guess a number $k$ less than $d$ and then check whether or not $k$ is a factor of $n$. (Can you see why you don't need to check whether $k$ is prime or not?)