🔢 Решето Ератосфена
Винайдений близько 240 р. до н.е. давньогрецьким математиком Ератосфеном, цей алгоритм знаходить усі прості числа до межі N. Починаючи з 2, він позначає всі кратні кожного простого як складені — будь-яке число, що залишається непозначеним, є простим. Спостерігайте, як виникає візерунок: прості числа світяться золотом, складені тьмяніють. Внизу — функція підрахунку простих π(x) ≈ x/ln(x). 🇬🇧 English
Вигляд
Теорема про прості числа
Теорема про прості числа (1896, Адамар і де ла Валле-Пуссен) стверджує: π(x) ~ x/ln(x) при x → ∞. Точніше наближення дає логарифмічний інтеграл li(x) = ∫₂ˣ dt/ln(t). Решето працює за час O(N log log N) — напрочуд швидко. Гіпотеза про прості-близнюки питає, чи існує нескінченно багато простих p, де p+2 — теж просте; це залишається недоведеним. Гіпотеза Рімана передбачає точний член похибки в π(x).