Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

shrohit_007's blog

Help me with this question
By shrohit_007, history, 4 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

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 \lt 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.

→ Reply