PolokN's blog

3 divisors
By PolokN, history, 6 years ago, In English

Suppose you need to find out which number has three divisors including itself and 1. For getting these numbers you don't need to check the divisors of that number. A number has 3 divisors if it is a square of a prime number. For example 4 is a square of prime number 2. Here 4 has 3 divisors. 1,2,4. The reason is the square of a prime number is divisible by 1 , the number itself, and the square root of that number that is a prime number. So if you need to find out the numbers that have 3 divisors only and you have time complexity matter then just generate the prime numbers using sieve method. After that just check whether the given number's square root is equal to any prime number or not. Hope this will help you.

  • Vote: I like it
  • +24
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Or you can find square root in O(logn) and then check if it is prime with some prime test like miller rabin.

→ Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

In general if a number has exactly p divisors, where p is a prime number, then it must be the (p-1)th power of some prime

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In similar, if you want to find 5 divisors numbers, you just check if the number is a power of 4 (i.e., x^4) of a prime number.

For example:

16 is 5-divisors number. here 16= 2^4

More over for 81, 81=3^4.

In this process, you can test, the numbers whose number of divisors are odd and prime (i.e., 3,5,7 etc).

→ Reply