>>43
NがM未満の素因数を持つか?っていう決定問題がPだと、二分探索をその桁数のオーダーだけやれば解けちゃうよ