UK 
EnglishТипова
Polski🔢 Решето Ератосфена — Анімований пошук простих чисел
Спостерігайте, як решето Ератосфена анімовано знаходить усі прості числа до 10000. Викреслюйте кратні кожного простого та відкривайте прості числа, функцію підрахунку π(x) і теорему про прості числа.
Схожі симуляції
Про решето Ератосфена
Ця симуляція безпосередньо реалізує класичне решето Ератосфена (близько 240 р. до н.е.): починаючи з булевого масиву, де всі значення 2…N позначені як істина, вона повторно знаходить наступний непозначений індекс p і — лише коли p² ≤ N — позначає кожне кратне p, починаючи з p², як складене число, пропускаючи вже виключені числа. Усе, що залишається непозначеним після завершення решета, є простим числом. Кожен крок анімації виконує один такий прохід позначення і перемальовує сітку (або спіраль Улама, яка розгортає числа 1…N назовні від центру) із простими числами золотистого кольору та поточним активним p — помаранчевого. Друга панель будує графік поточної функції підрахунку простих чисел π(x) — кількості знайдених на даний момент простих — порівняно з класичною оцінкою x/ln(x), дозволяючи спостерігати, як проявляється теорема про прості числа зі зростанням N.
🔬 Що це показує
Живе булеве решето на цілих числах від 2 до N (до 10 000): непозначені виживші числа є простими, а кратні кожного щойно знайденого простого p викреслюються, починаючи з p² (менші кратні вже викреслені меншими простими числами). Графік під сіткою порівнює фактичну кількість π(x) з x/ln(x) — асимптотичною оцінкою теореми про прості числа.
🎮 Як користуватися
Перетягніть Limit N, щоб обрати, скільки цілих чисел просіювати, і Anim speed, щоб керувати кількістю кроків за кадр. Перемикайтеся між макетом Grid (сітка) та Ulam Spiral (спіраль Улама) кнопками перегляду. Натисніть Start, щоб анімувати решето крок за кроком, Instant, щоб розв'язати миттєво, або Reset, щоб перебудувати масив з нуля.
💡 Чи знали ви?
Решету потрібно перевіряти кандидатів у прості числа p лише до √N, і кожне з них пропускається, якщо вже було позначене складеним меншим простим числом — саме тому його час виконання надзвичайно ефективний, O(N log log N), один із найшвидших відомих способів перерахувати всі прості числа нижче межі.
Часті запитання
Чому позначення починається лише з p², а не з 2p?
Будь-яке складене кратне p, менше за p² — наприклад, 2p, 3p, …, (p−1)p — уже має простий множник, менший за p, тому воно було викреслено на попередньому проході, коли оброблявся той менший простий множник. Початок кожного проходу з p² пропускає надлишкову роботу і є ключовою оптимізацією, яка надає решету час виконання O(N log log N) замість повільнішого O(N log N).
Як спіраль Улама пов'язана з цим решетом?
Перегляд спіралі Улама використовує той самий масив решета, що й перегляд сітки, але перебудовує кожне просте число, що вижило, уздовж квадратної спіралі, яка розгортається назовні від центру, по одній клітинці на кожне ціле число. Візуально прості числа мають тенденцію групуватися вздовж певних діагональних ліній у цьому макеті — вражаючий, досі не повністю пояснений патерн, вперше помічений математиком Станіславом Уламом у 1963 році під час нудної конференційної доповіді.
Що означає графік π(x) відносно x/ln(x)?
π(x) — це функція підрахунку простих чисел: фактична кількість простих чисел, менших або рівних x, підрахована безпосередньо решетом під час роботи. x/ln(x) — це асимптотичне наближення провідного порядку з теореми про прості числа (доведеної незалежно Адамаром і де ла Валле-Пуссеном у 1896 році). Обидві криві дедалі точніше збігаються зі зростанням N, що саме й передбачає теорема — хоча відношення прямує до 1 лише в границі x → ∞.
Чому решето виконується за час O(N log log N)?
Загальна робота пропорційна N, помноженому на суму 1/p за всіма простими числами p ≤ √N (один "удар" на кожне кратне кожного простого числа). За другою теоремою Мертенса сума обернених значень простих чисел до межі зростає як логарифм логарифма цієї межі, тож загальна робота масштабується як N·log log N — асимптотично близько до лінійної і набагато швидше, ніж пробний поділ кожного числа окремо.
Що відстежує статистика найбільшого проміжку між простими числами?
Вона показує найбільшу різницю між послідовними простими числами, знайденими до поточної межі N (наприклад, проміжок 8 між 89 і 97). Проміжки між простими числами зростають нерегулярно, але в середньому розширюються як ln(N) зі зростанням N, згідно з теоремою про прості числа; недоведена гіпотеза Крамера пропонує жорсткішу межу для того, наскільки великим може бути окремий проміжок, але вона залишається недоведеною.
Чи доводить або спростовує це решето гіпотезу про прості числа-близнюки?
Ні — решето може перерахувати кожну пару простих чисел-близнюків (p, p+2) нижче обраної межі N, але це лише підтверджує скінченну кількість прикладів. Гіпотеза про прості числа-близнюки стверджує, що існує нескінченно багато таких пар серед усіх простих чисел, що є твердженням про всі прості числа, а не скінченним обчисленням; попри вагомі числові та часткові теоретичні докази (включно з проривом Чжана 2013 року щодо обмежених проміжків), вона залишається відкритою проблемою теорії чисел.