Каталог@Mail.ru - каталог ресурсов интернет

Сколько простых чисел среди натуральных?

На главную Понятие простых чисел О получении простых чисел Другие статьи

В данной статье попытаемся дать оценку, каков процент простых чисел среди натуральных.


Для этого нам понадобятся признаки делимости, теории множеств и вероятностей и простая трезвая логика.

Шаг 1. Сначала проще всего отсечь составные числа, делящиеся на 2 и/или на 5.


По Шагу 1 простыми не могут быть числа из двух и более цифр, оканчивающиеся на 0, 2, 4, 5, 6, 8. Стало быть, простыми числами, имеющими значение не менее 10, могут быть числа, у которых последняя цифра 1, 3, 7 или 9. Итог: простых чисел не может быть более F(1)=40% от всех натуральных чисел.

Шаг 2. Из чисел, оканчивающихся на 1, 3, 7, 9, отсеем числа, которые делятся на 3.


Проще всего Шаг 2 выполнить, выписав несколько групп чисел, "выживших" после Шага 1, и посмотреть, как часто встречаются среди них составные числа, делящиеся на 3.

11131719
21232729
31333739
41434749
51535759
61636769


В итоге отсеиваем каждое третье число из тех, которые не менее 10 и оканчиваются на 1, 3, 7, 9. Среди чисел от 1 до 9 этот шаг не выполняется, но в пределе - при отсеве из бесконечного количества натуральных чисел - это не внесёт никакого вклада.

Шаг 2 можно было выполнить, воспользовавшись признаком делимости на 3 - подсчитав, какова вероятность того, что сумма цифр числа, оканчивающегося на 1, 3, 7 или 9, будет кратна тройке. Но этот путь посложнее и никаких преимуществ не даст.

На первом шаге осталось 40% чисел. Из них треть отсеяна на втором шаге. Итого выходит, что простыми числами могут быть не более F(2) = 26,67% натуральных чисел.

Шаг 3. Из чисел, оставшихся после Шага 2, отсеиваем числа, делящиеся на 7.


Среди чисел, оканчивающихся на 1, 3, 7, 9, каждое седьмое кратно 7. Это обусловлено тем, что если взять случайное натуральное число N и загнать его в формулу X = (7N mod 10), то X - с равной вероятностью любая цифра. Для наглядности изобразим небольшую табличку. Посмотрите на неё внимательно и убедитесь, что тут написано не враньё.

111317192123272931333739
414347495153575961636769
717377798183878991939799
101103107109111113117119121123127129
131133137139141143147149151153157159
161163167169171173177179181183187189
191193197199201203207209211213217219


Указанный факт со случайным числом приводит к следующему. Пусть X(q) - количество чисел, оканчивающихся на цифру q и делящихся на 7. Тогда X(1) = X(3) = X(7) = X(9). Такое же равенство мы бы получили, если бы рассматривали числа, делящиеся на 3:

111317192123272931333739
414347495153575961636769
717377798183878991939799


Выходит, что среди чисел, оканчивающихся на 1, 3, 7, 9 и делящихся на 7, треть была учтена при Шаге 2. Для наглядности ещё одна табличка:

111317192123272931333739
414347495153575961636769
717377798183878991939799
101103107109111113117119121123127129
131133137139141143147149151153157159
161163167169171173177179181183187189
191193197199201203207209211213217219


Итого процент оставшихся чисел уменьшается на 40 * (1/7) * (2/3). Итого осталось более 40 * (2/3) * (6/7) процентов чисел, то есть F(3) = 22,86%.

Шаг 4. Теперь исключим числа, кратные 11.


Из чисел, оканчивающихся на 1, 3, 7, 9, каждое 11-ое кратное 11. При этом требуется учесть только числа, не делящиеся ни на 3, ни на 7. Пусть p(x) - вероятность того, что случайное натуральное число делится на x. Вероятность того, что случайное натуральное число не делится ни на 3, ни на 7, равна 1 - (p(3) + p(7) - p(21)) = 1 - (1/3 + 1/7 - 1/21) = 4/7. В итоге процент оставшихся чисел уменьшается на 40 * (1/11) *(4/7). Итого доля простых чисел не будет более 20,8%.

С учётом кратности 13 и более крупным простым числам следует полагать, что доля простых чисел среди натуральных не может быть более 20%.


Желающие могут продолжить шаги по нашему методу) Дальнейшие действия выполняются по аналогии с теми, что были выполнены. Далее следует брать более крупные простые делители - 13, 17, 19 и т.д. Это не даст точной оценки, но даст всё более точное приближение к ней.

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X