Here are some useful conclution for naive algorithms to solve number theory problem,I hope you can know something about it and solve number theory problems more easily.
1.The number of prime factors of an intelliger
It's sure that the number of prime factors of an intelliger is very small,and an intelliger $$$v$$$ can be divided into $$$\log_2(v)$$$ primes.This can be used for bruteforce and State compression.
example:510D.
2.The number of factors of an intelliger
First of all,$$$\sum_{i = 1} ^ n \operatorname{d}(n) = \sum_{i = 1} ^ n [\frac{n}{i}] \approx n \ln n$$$.
Then I've found out that the number of factors of an intelliger($$$\operatorname{d}(n)$$$) is usually small,and to make sure,I made a code to get the maxinum number of the number of factors,and get:
- For $$$n \le 10 ^ 4,\max \operatorname{d}(n) <= 68$$$;
- For $$$n \le 5 \times 10 ^ 4,\max \operatorname{d}(n) <= 100$$$;
- For $$$n \le 10 ^ 5,\max \operatorname{d}(n) <= 128$$$;
- For $$$n \le 2 \times 10 ^ 5,\max \operatorname{d}(n) <= 160$$$;
- For $$$n \le 3 \times 10 ^ 5,\max \operatorname{d}(n) <= 180$$$;
- For $$$n \le 5 \times 10 ^ 5,\max \operatorname{d}(n) <= 200$$$;
- For $$$n \le 10 ^ 6,\max \operatorname{d}(n) <= 240$$$;
- For $$$n \le 5 \times 10 ^ 6,\max \operatorname{d}(n) <= 384$$$;
- For $$$n \le 10 ^ 7,\max \operatorname{d}(n) <= 448$$$;
So if your solution of a problem is $$$\operatorname{O}(n\max \operatorname{d}(a_i))$$$ or $$$\operatorname{O}(\sum \operatorname{d}(a_i))$$$,it might be correct because for $$$a_i \le 10 ^ 7$$$,it's sure that $$$\operatorname{d}(a_i) \le 500$$$.
examples:
3.Euler's Function: $$$\operatorname{O}(\log_2 n)$$$ times to $$$1$$$.
It's sure that $$$\phi(n) \le \frac{n}{2}$$$ for $$$2 | n$$$,and $$$2 | \phi(n)$$$ for $$$n > 1$$$.So if you use operation $$$x = \phi(x)$$$ for $$$x = n$$$ initially,it will become $$$1$$$ in $$$\operatorname{O}(\log_2 n)$$$ times.
example:906D.
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Question: why "intelliger" instead of "integer"? Is it an implication that integers are intelligent and sentient beings?
A slight correction on 1: the growth is in fact just $$$\mathcal{O}(\log \log n)$$$ on average.
I think he was talking about the worst case relating to (not necessarily distinct) prime factors, since oftentimes the worst case is of greater importance in competitive programming.
I'm curious about the worst case when we count distinct prime factors though — the wikipedia page you linked says that $$$\omega(n) \sim \frac{\log n}{\log \log n}$$$ when $$$n$$$ is a primorial, but I can't see how one would come up with this approximation :/
Ah, I see. I tend to only consider distinct ones (non-distinct can be compressed in map form), so was kinda misreading that part.
For your concern, I looked at the citation which wrote:
Probably the document they meant to mention was
G. H. Hardy and E. M. Wright (2006). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press.
.oh wow, I totally forgot about references lol. I took a look at it, and it makes way more sense now. Thanks!
gcd(x, y) = min(x, y) or gcd(x, y) <= min(x, y) / 2. so we can say there are O(lg(n)) distinct prefix gcds.
Man, I don't know. Maybe it's just preference, but I don't think "intelliger" is a word.