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

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

This is an example of problem form Russian state exam, you have to precompute unswer and fill in blank with this answer, you are given 4 hours for the whole exam, and this one is not the hardest, can someone please me help with fast solution.

Find all integer number on the segment [106 000 000, 107 000 000] which have 3 different even dividers. Put this numbers in the answer.

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

»
3 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Try to print all the integers divisible by 8 in this range.

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

    this is not gonna work, just consider that it has 2 4 8 and number itself are even dividers, it is already more than 3

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    It does not work (see the answer below). Also, most likely the author meant ``exactly 3 different even divisors''.

»
3 года назад, # |
Rev. 4   Проголосовать: нравится +17 Проголосовать: не нравится

Let's write the number in the form $$$2^kr$$$ where $$$r$$$ is odd. The number of even divisors is then $$$k\cdot d(r)$$$. Thus, $$$k$$$ can be $$$1$$$ or $$$3$$$. If it is $$$3$$$, then $$$d(r)=1 \implies r=1$$$, which is impossible in the given range.

Now we know that $$$k=1$$$ and $$$d(r)=3$$$. The latter can only happen when $$$r$$$ is a square of some prime number $$$r=p^2$$$. Finally, to find all such numbers, you should iterate over all even numbers in the given range, divide them by $$$2$$$, check whether the quotient is a perfect square, and finally check whether its square root is prime. To check whether $$$\sqrt{r}$$$ is prime you can either use a brute-force solution (you will only check numbers up to $$$\approx 100$$$) or precompute all prime numbers up to $$$\approx 10^4$$$.