Xác suất nào để cho một số nguyên là số nguyên tố?
Ta ghi π(n) là số của các số nguyên tố nhỏ hơn số nguyên n. Sự tiến triển của các giá trị π(n) theo n là một chỉ số của ''tỷ lệ'' mà các số nguyên tố có trong tập hợp của tất cả các số nguyên. Ta có thể rút ra cách lập luận của Euclide và Pólya đã nêu ở trên là, đối với mọi số nguyên n, π(n) luôn luôn ít nhất bằng log2(log2(n), trong đó log2(x) là luỹ thừa theo đó phải tăng giá trị 2 để thu được x (nói cách khác, 2log2 = x; ví dụ, log2(4) = 2, log2(32) = 5, v.v...), Lợi ích duy nhất của kết quả này là chứng minh nó đơn giản, vì cụ thể là nó chỉ dẫn đến các ước tính không đáng kể: trong khi có hơn 50 triệu số nguyên tố giữa 1 và 1 tỷ, thì trong khoảng này, tất cả những gì đảm bảo bất đẳng thức của chúng ta là lượng số nguyên tố ít nhất cũng là... 3! Vì vậy, bất đẳng thức này không đủ để khoanh tỷ lệ của những số nào là số nguyên tố.
Kết quả giải quyết vấn đề này được biết dưới tên là định lý số nguyên tố. Được Gauss phỏng đoán vào đầu thế kỷ XIX, được Tchebycheff chứng minh một phần năm 1850 và được Hadamard và de la Vallée Poussin chứng minh hoàn toàn năm 1896, cái quý giá này của số học khẳng định rằng π(n) gần với tỷ số n/1oge(n), trong đó lần này loga có ''cơ số e", nghĩa là trong định nghĩa trước của loga, cần thay giá trị 2 bằng giá trị e (khoảng 2,718), được gọi là “cơ số loga Neper”. Người ta rút ra từ định lý này là, trong số tất cả các số nguyên nhỏ hơn số nguyên n, thì tỷ lệ những số là số nguyên tố bằng 1/loge(n): tỷ lệ này ngày càng nhỏ khi n ngày càng lớn. Khi ta nhìn vào những số ngày càng lớn, thì ta thường thấy số nguyên tố ngày càng giảm, cho dù người ta biết rằng nguồn này không bao giờ cạn.
