Яка швидкість виконання завдання по знаходженню кількості простих чисел до мільярда?

1. Використавши теорему про розподіл простих чисел, отримаємо таку асимптотическую оцінку: x/lnx=48 254 942 - 1 сек. якщо вважати на звичайному калькуляторі.

2. Застосуємо гіпотезу про інтегральний логарифм. Отримаємо інтеграл: int (dx/lnx) в межах інтегрування від 1 до мільярда. Він дасть такий чисельний результат 50 849 235 - 1 сек. Результат набагато точніше, але має свою похибку. І істотний недолік: цілком спирається на недоведеною гіпотезу Рімана. Так що не факт, що ця оцінка: 1) завжди буде точна; 2) ніколи не стане точно дорівнює кількості простих чисел для будь-якого їх числа починаючи з якогось моменту.

Точне число простих чисел до мільярда 50 847 534. Це теж свого роду алгоритм: гугленіе таблиці кількості простих чисел до деякого заданого числа. Якщо таблиця під рукою: вимагає менше секунди, поки комп’ютер шукає. Ясно, що це жартівливий алгоритм. Але чому б і ні? )

Використавши решето Аткіна, отримаємо точне числопростих чисел за менший час в порівнянні з деякими іншими алгоритмами (на кшталт решета Ератосфена). Даний алгоритм має асимптотичну складність О (x/ln (ln (x)). На вхідних значеннях порядку 10 ^ 9 решето Аткіна швидше решета Ератосфена в 9.2 рази. Розглянемо, скільки часу йому потрібно для деяких значень х:

10 000 000 вимагає 0.15 сек.

100 000 000 займає вже 2.16 сек

1 000 000 000 чисел, як заявлено в умови, вимагає для точного підрахунку вже 48.76 сек. для порівняння: деякі реалізації решета Ератосфена вимагають приблизно 10 хвилин.

Тим самим: застосовуючи інтегральний логарифм, ми отримаємо асимптотическую оцінку з деякою похибкою ністю всього за 1 секунду, а застосовуючи решето Аткіна, отримаємо точний результат майже за 49 секунд




ЩЕ ПОЧИТАТИ