Math
Решето і щільність простих
Проведіть решето вручну на пронумерованих плитках: візьміть наступний дільник, передбачте, звідки почнеться його хвиля, і дивіться, як вона викреслює кратні — уже викреслені лише зачіпаються. Поруч — pi(x) за підрахунком проти наближень x/ln x і Li(x).
Що відбувається
Решето Ератосфена на дошці пронумерованих плиток. Візьміть наступний дільник — найменшу ще стоячу плитку — і скажіть, звідки почнеться його хвиля: перше ще стояче кратне — завжди p², бо кожне менше кратне k·p має менший дільник k і вже викреслене. Потім хвиля проходить по p², p² + p, …: стоячу плитку вона викреслює, і та бере колір цього простого; уже викреслену лише зачіпає й рахує, але не викреслює знову. Знайдені прості збираються в рядок під дошкою. Решето зупиняється, коли квадрат наступного дільника виходить за дошку — будь-яке складене до N має дільник не більший за √N, — і все, що ще стоїть, — прості. На великій дошці плитки стають щільною картою, а лупа під курсором читає числа. Графік поруч рахує pi(x) до своєї межі проти двох наближень, x/ln x і Li(x): грубе занижує на відсотки, Li майже лежить на підрахунку, а 60180 — останнє N до двох мільйонів, де x/ln x помиляється більш ніж на десять відсотків.
Рівняння модуля
Рівняння решето рахує pi(N) точно - це означення, а не оцінка pi(10^3) = 168, pi(10^4) = 1229, pi(10^5) = 9592, pi(10^6) = 78498 N / ln N ЗАНИЖУЄ: при 10^3 на 13.83 %, при 10^4 на 11.66 %, при 10^5 на 9.45 %, при 10^6 на 7.79 % Li(N) = інтеграл від 2 до N виразу dt/ln t помиляється на частки відсотка: 5.098 %, 1.309 %, 0.383 %, 0.164 % на тих самих порядках Li(10^4) = 1245.092052, Li(10^6) = 78626.503996 завдання: 60180 є ОСТАННІМ N до двох мільйонів, де N/ln N відхиляється більш ніж на десять відсотків (10.0004 %); при 60181 воно становить 9.9990 % - знайдено ОДНИМ ПРОХОДОМ за префіксними лічильниками, бо похибка НЕ монотонна: вона перетинає лінію десяти відсотків 159 разів, а бісекція, що стояла тут раніше, відповідала 60180 вартість решета, дві РІЗНІ величини: перші викреслення = N − pi(N) − 1 РІВНО (8770 при 10^4, 921501 при 10^6) - кожне складене число викреслюється вперше рівно один раз усього звернень ~ сума N/p по p <= sqrt(N) (16981 проти 18028 при 10^4, відношення 0.9419; 0.9654 при 10^6) - решето починає з p² і ніколи не торкається менших кратних найбільший розрив між простими: 8 після 89, 20 після 887, 36 після 9551, 72 після 31397 - усі ще нижчі за ln²N
