# Number of divisors of a number - in NP?

I'm trying to show that the language {(m,n)|m has exactly n divisors} is in NP.

The input (m,n) is in binary.

The non-deterministic Turing machine for the language would be:

1) Guess the prime factors of m.

2) Verify that ∏i(di+1)=n.

The problem is that I can't find a way to factorize in polynomial time (in the input) the number m.

If stage 1 takes m steps then it would be m=2 ^ log(m) and the whole algorithm would run in exponential time.

How can I prove that verifying that m has exactly n divisors is in NP ? Perhaps not via factorization but somehow else. I've run out of ideas.

• You seem to be misunderstanding the difference between P and NP. An NP machine doesn’t have to compute a factorization in polytime - it just as to be able to verify a given factorization in polytime. To this end, it’s useful to know that primality testing is in P. – Yuval Filmus Dec 15 '18 at 9:52
• @YuvalFilmus I know that i can get a certificate and just verify it but what would it be ? If the certificate is the list of prime factors then i need to check if it is of length O(log(m)) but how long do i run to check its length - 2logm, 3 logm, 4logm... ? – caffein Dec 15 '18 at 10:00
• @YuvalFilmus Also, how do i prove that the number of prime factors of m is log(m) ? If it is longer then the whole machine would run in non polynomial time – caffein Dec 15 '18 at 10:02
• Take it as an exercise. Use $2^{\log m} = m$. – Yuval Filmus Dec 15 '18 at 10:02
• The problem is that i need a formal proof and after googling it doesn't seem trivial at all - to prove that a number with m digits has O(log(m)) prime factors. – caffein Dec 15 '18 at 10:10