Блог пользователя PolokN

3 divisors
Автор PolokN, история, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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).

→ Ответить