Простые числа вида k * 2 n +1
Как видите, менее чем за 5 секунд удалось отбраковать более 66% чисел! Давайте попробуем увеличить таблицу.
t=Sort[DeleteCases[Array[f3.25.3],Null]] {{3.1},{4.3},{10.7),{12.2},{18.14),{28.9},{36.28),{39.29}, {48.5},{51.4 2},{52.9},{58.37},{60.24},{66.60},{82.51},{100.81}}Опять считаем процент отбракованных чисел и замеряем время.
prog //Timing Yes= 25645; No= 74355{7.188 Second, Null}Время отбраковки возросло чуть более чем на 2 секунды, а отбраковали мы более 74% чисел! Значит, таблицу стоит увеличить.
t=Sort[DeleteCases[Array[f3.100.3], Null]];Опять измеряем время.
prog //Timing Yes = 21055; No= 78945{14.765 Second, Null}Как видим, таблицу увеличивать стоило! Время отбраковки, конечно, возросло, притом более чем вдвое, но 15 секунд по сравнению с часами счета роли не играют. Так что увеличение таблицы окупает себя! Увеличиваем таблицу еще.
t=Sort[DeleteCases[Array[f3.1000.3],Null]];Теперь снова измеряем время и процент отбраковки.
prog //Timing Yes= 15388; No= 84612{84.64 Second, Null}Конечно, время возросло: теперь отбраковка занимает более одной минуты. Но проверять по-настоящему придется чуть более 15% чисел! Потратив дополнительно на предварительную отбраковку немногим более одной минуты, мы почти в 8 раз уменьшим количество чисел, которые надо будет проверить на простоту. Так что увеличение таблицы оправдало себя и на этот раз. Поэтому еще раз увеличиваем таблицу.
t=Sort[DeleteCasestArray[f3,10000.3],Null]]; //Timing {90.703 Second, Null}На этот раз сама генерация таблицы занимает более полутора минут. Но и это время окупается.
prog //Timing Yes = 12123; No= 87877{630.734 Second, Null}Количество чисел, которые подлежат проверке на простоту, мы уменьшили более чем в 8 раз! Может быть, стоит увеличить таблицу еще? Ну, на этот раз, во всяком случае, уж точно не в 10 раз. Ведь ждать генерации таблицы несколько часов – занятие весьма неприятное! Поэтому лучше сначала попытаться увеличить таблицу, скажем, в 2.5 раза.
t=Sort[DeleteCases[Array[f3.25000.3],Null]]; //Timing {629.781 Second, Null}На генерацию таблицы понадобилось почти десять с половиной минут. Заметно, что время генерации таблицы растет нелинейно с ростом таблицы. Наверное, нужно проверить, не пора ли остановиться.
prog //Timing Yes= 11129; No= 88871{1405.2 Second, Null}На отбраковку потрачено почти двадцать четыре минуты. Это существенно больше, чем в предыдущем случае. Несмотря на это, дополнительно отбраковать удалось чуть более одного процента чисел. Кажется, пора остановиться. (Конечно, это довольно грубый и притом субъективный критерий останова.)
Теперь можем приступить к написанию программы. Пусть ее заголовок (имя и список параметров) будет М3n[n_]. (Параметр n – верхний конец диапазона, в котором происходит перебор.) Прежде всего нужно решить следующий вопрос: как использовать таблицу так, чтобы не пропустить ни одного простого числа вида 3*2n +1 даже в том случае, если оно использовалось при построении таблицы. Конечно, можно заблаговременно составить список n для таких чисел. Но это значит, что список п для таких чисел нужно составить по другой программе, решающей фактически ту же задачу, "решением которой мы сейчас как раз и заняты.