The number of different factors of 3003 is equals to?

Question

I'm solving a book and it has similar 5-6 questions like this although the answer is provided but no solution as for how to obtain or what rule to use is given, how shall I approach this problem? Also it'd amazing if anyone can help me understand my previous problem as well since I am not satisfied with the answers there, thanks.

The number of divisors of 2700 including 1 and 2700 equals

Answer 1

You can find the prime factors by trial division, which doesn't take very long, to get $3003 = 3 \times 7 \times 11 \times 13$. Now, if you have a number and its prime factorisation, $n = p_1 ^{m_1} p_2^{m_2} \cdots p_r^{m_r}$, you can make divisors of the number by taking up to $m_1$ lots of $p_1$, up to $m_2$ lots of $p_2$ and so on. The number of ways of doing this is going to be $(m_1 + 1)(m_2 + 1) \cdots (m_r + 1)$. In particular, $3003$ has $2^4 = 16$ divisors.

Answer 2

Observe that $3003=3\cdot 7\cdot 11\cdot 13$. Since the number of divisors function is multiplicative (in a number theory sense - make sure to read up about powers of primes). Additional details can be found at multiplicative function.

Then you're looking for the divisor function (which is multiplicative): $$ \sigma_0(3003)=\sigma_0(3)\sigma_0(7)\sigma_0(11)\sigma_0(13)=2\cdot 2\cdot 2\cdot 2=16. $$

Answer 3

Numbers of that size should not take long even with a low-tech approach.

Divide by 2 if you can, repeat dividing by 2 until you cannot. In this case, you cannot.

Now divide by 3 if you can and, again, repeat. In this case you can once: 3003 = 3 x 1001.

Continue through the primes: skip 4 and all of the other even numbers as they are not prime. 5 not in this case.

Another answer appeared as I was typing saving me from having to divide by 7. In this case, you can divide by 7.

Each time that you find a factor, the next step gets easier.

If you are really unlucky, the number is prime. You can stop when you get to the square root as if you have not found one by then then you won't find one. You don't need to exactly calculate the square root but once you try a number whose square exceeds the number you are testing then you can stop.

When you have finished, you have the prime factors. To find all factors, prime or not, you need to consider what distinct combinations are possible.