Как с этим бороться

Во-первых, можно поучится быстрее осуществлять проверку на делимость одного числа на другое, во-вторых можно попытаться число А подбирать таким образом, чтобы оно было простым с высокой степенью вероятности. Оказывается это возможно. Математик Мерсен обнаружил, что числа следующего вида

2ⁿ - 1

Являются простыми с высокой степенью вероятности.

Чтобы понять написанную выше фразу, посчитаем, сколько простых чисел находится в первой тысяче, и сколько чисел Мерсена в этой же тысяче являются простыми. Итак, числа Мерсена в первой тысяче - это следующие:

2¹ - 1 = 1; 2² -1 = 3; 2³ - 1 = 7; 2⁴ - 1 = 15; 2⁵ - 1 = 31; 2⁶ -1 = 63;

2⁷ - 1 =127; 2⁸ -1 = 255; 2⁹ - 1 = 511;

Жирным шрифтом помечены простые числа. Всего на 9 чисел Мерсена 5 простых. В процентах это 5/9*100 = 55,6%. В то же время на 1000 первых натуральных чисел только 169 простых. В процентах это 169/1000*100 = 16,9%. То есть в первой тысяче в процентом отношении простые среди чисел Мерсена встречаются почти в 4 раза чаще, чем среди просто натуральных чисел

А теперь возьмём конкретное число Мерсена, например 2⁴ - 1. Запишем его в виде двоичного числа.

2⁴ - 1 = 10000 - 1 = 1111

Возьмём следующее число Мерсена 2⁵ -1 и запишем его двоичным числом. Получим следующее:

2⁵ -1 = 100000 - 1 = 11111

Уже видно, что все числа Мерсена представляют собой последовательность единиц, и уже сам этот факт даёт большой выигрыш. Во-первых, в двоичной системе счисления очень просто получить очередное число Мерсена. Для этого достаточно к очередному числу дописать единицу. Во-вторых, искать делители в двоичной системе на много проще, чем в десятичной.

Не нашли, что искали? Воспользуйтесь поиском: