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

Help me with this question
Автор shrohit_007, история, 21 месяц назад, По-английски

the question is very simple we just need to calculate total number of numbers which have exactly 4 divisors for ex 6, 8, 10 these are all of the forms p^3 or p*q but here n<=10^11

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by shrohit_007 (previous revision, new revision, compare).

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

Here $$$\pi(n)$$$ denotes prime counting function, i.e number of primes not greater than $$$n$$$.

Numbers form $$$p^3$$$ can be easily counted, it's just $$$\pi \left(\lfloor \sqrt[3]{n} \rfloor\right)$$$.

To calculate numbers form $$$pq$$$ recall, that

$$$ \sum\limits_{k = 1, k = pq}^n 1 = \sum\limits_{p \leqslant n} \sum\limits_{p < q \leqslant \frac{n}{p}} 1 = \sum\limits_{p \leqslant \sqrt{n}} \pi \left( \lfloor \frac{n}{p} \rfloor \right) - \pi(p)$$$

.

Primes and $$$\pi$$$ up to $$$\sqrt{n}$$$ can be calculated straightforward using Eratosphenes sieve.

Also you can calculate values of $$$\pi\left( \lfloor \frac{n}{k} \rfloor \right)$$$ for all $$$k \geqslant 1$$$ using $$$O(n^{2/3})$$$ time as described here https://codeforces.me/blog/entry/91632

IMHO this question is not very simple as it requires some knowledge.

→ Ответить