Bài toán 1 : CMR : ~O\left( \frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n} \right)\approx O({{\log }_{2}}n)~

----------

~{{H}_{n}}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}~
~{{H}_{n}}=\frac{1}{1}+\left( \frac{1}{2}+\frac{1}{3} \right)+\left( \frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7} \right)+...+\left( \frac{1}{{{2}^{k}}}+...+\frac{1}{n} \right)\, với\, k=\left\lfloor {{\log }_{2}}(n) \right\rfloor ~ là số nguyên lớn nhất mà ~2^k \leq n~
~{{H}_{n}} < 1+1+...+1 <{{\log }_{2} }(n)+1~
~\Rightarrow {{H}_{n}}\le {{\log }_{2}}(n)~ hay ~O\left( \frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n} \right)\approx O({{\log }_{2}}n)~

----------
Bài toán 2: ĐPT của thuật toán sàng nguyên tố Erathosenes

Theo 1 số định lý và đánh giá chặn trên (upper bound) nữa (vì khó quá nên xin không chứng minh ở đây) của Meissel–Mertens
~\underset{n\to +\infty }{\mathop{\lim }}\,\left( \sum\limits_{p\text{ prime}}^{p\le n}{\frac{1}{p}}-\ln \left( \ln (n) \right) \right)=0.261497\ldots ~ hay với n đủ lớn ~\sum\limits_{p\text{ prime}}^{p\le n}{\frac{1}{p}}\approx \ln \left( \ln (n) \right)+0.261497\ldots ~
Vì thế nên ĐPT của thuật toán sàng nguyên tố Erathosenes cũng không quá lớn, vào khoảng $$O\left( n+n\sum\limits_{p\text{ prime}}^{p\le n}{\frac{1}{p}} \right)\approx O\left( n\left( \ln \left( \ln (n) \right)+1.261497\ldots \right) \right)$$ Và các bạn cũng nên biết ~n={{10}^{8}}~ thì ~ \ln \left( \ln (n) \right)\approx 2.91~
----------

Bài toán 2.2(Euler): Chứng minh ~\prod\limits_{p\le n}{\frac{p}{p-1}}\ge \sum\limits_{i=1}^{n}{\frac{1}{i}}~
Chứng minh:

Theo định lý cơ bản của số học, 1 số nguyên dương n chỉ có duy nhất 1 cách phân tích dưới dạng tích các số nguyên tố không vượt quá n, nên
~\sum\limits_{i=1}^{n}{\frac{1}{i}}=\prod\limits_{p\le n}{\left( 1+\frac{1}{p}+\frac{1}{{{p}^{2}}}+\cdots \right)}\le \prod\limits_{p\le n}{\sum\limits_{i=0}^{+\infty }{\frac{1}{{{p}^{i}}}}}=\prod\limits_{p\le n}{\frac{p}{p-1}}(dpcm)~

----------
Bài toán 3: Đặt ~\pi(n)~ là số số nguyên tố không vượt quá ~n~.
Khi đó theo Định lý số nguyên tố ~ \pi(n) \approx \frac{n}{ln(n)} ~ hay ~O\left( \pi(n) \right) \approx O \left(\frac{n}{ln(n)} \right)~