Is there a polynomial time algorithm for this decision problem? Is there a factor in $M$ that is $&gt;$ $1$, but $&lt;$ $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 $&gt;$ $1$ but &lt; $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 &lt; $M$

Question

I have found a pseudo-polynomial solution, but is there a polynomial solution for this problem in the length of input?
This is hard as the integer factoring problem (simply take $N$ to be 2 or a random prime that has no factor in common with $M$).  Whether there is a polynomial-time algorithm for factoring is a famous open problem, but it is widely believed that there likely is no such algorithm.