Is there a factor in $M$ that is $>$ $1$, but $<$ $M$ that is NOT a factor of $N$?
False Result Example
$N$ = 8
$M$ = 16
1, 2, 4, 8, 16
There is no integer that is NOT a factor of $N$ that is $>$ $1$ but < $M$
True Result Example
$N$ = 2
$M$ = 26
1, 2, 13, 26
There is an integer $13$ which is NOT a factor of $N$ that is > 1 but < $M$
I have found a pseudo-polynomial solution, but is there a polynomial solution for this problem in the length of input?