Иллюстрированный самоучитель по Mathematica 5

Простые числа вида k * 2 n +1

Опять считаем процент отбракованных чисел и замеряем время:

prog //Timing 
Yes= 23152; No= 76848
{6.985 Second, Null}

Время отбраковки возросло менее, чем на 2 секунды, а отбраковали мы почти 77% чисел! Значит, таблицу стоит увеличить.

t=Sort[DeleteCases[Array[L,100.4],Null]];

Опять измеряем время:

prog //Timing 
Yes = 18329; No= 81671 
(14.047 Second, Null}

Как видим, таблицу увеличивать стоило! Время отбраковки, конечно, возросло, притом более чем вдвое, но 14 секунд по сравнению с часами счета роли не играют. Так что увеличение таблицы окупает себя! Увеличиваем таблицу еще.

t=Sort[DeleteCases[Array[f,1000.4],Null]];

Теперь снова измеряем время и процент отбраковки:

prog //Timing 
Yes=12827; No= 87173 
{74.172 Second, Null}

Конечно, время возросло: теперь отбраковка занимает более одной минуты. Но проверять по-настоящему придется менее 13% чисел! Потратив дополнительно на предварительную отбраковку чуть более минуты, мы почти в 8 раз уменьшим количество чисел, которые надо будет проверить на простоту. Оказывается, увеличение таблицы оправдало себя и на этот раз. Поэтому еще раз увеличиваем таблицу.

t=Sort[DeleteCases[Array[f,10000.4],Null]]; //Timing
{89.969 Second, Null}

На этот раз сама генерация таблицы занимает более минуты. Но и это время окупается.

prog //Timing 
Yes= 9821; No= 90179
{527.781 Second, Null)

Количество чисел, которые подлежат проверке на простоту, мы уменьшили более чем в 10 раз! Может быть, стоит увеличить таблицу еще? Ну, на этот раз, во всяком случае, уж точно не в 10 раз. Ведь ждать генерации таблицы несколько часов – занятие весьма неприятное! Поэтому лучше сначала попытаться увеличить таблицу, скажем, в 2.5 раза.

t=Sort[DeleteCases[Array[f,25000.4],Null]] //Timing
{638.234 Second, Null}

На генерацию таблицы понадобилось более десяти с половиной минут. Заметно, что время генерации таблицы растет нелинейно с ростом таблицы. Наверное, пора остановиться. Проверяем:

prog //Timing 
Yes= 8985; No= 91015
{1201.44 Second, Null}

На отбраковку потрачено более двадцати минут. Это на 9.39063 минут больше, чем в предыдущем случае. Несмотря на все это, дополнительно отбраковать удалось менее одного процента чисел. Действительно, пора остановиться. (Надо признать, конечно, что это довольно грубый, притом субъективный критерий останова.)

Теперь можем приступить к написанию программы. Пусть ее заголовок (имя и список параметров) будет М5п[п_]. (Параметр n – верхний конец диапазона, в котором происходит перебор.) Прежде всего нужно решить следующий вопрос: как использовать таблицу так, чтобы не пропустить ни одного простого числа вида 5-2n +1 даже в том случае, если оно использовалось при построении таблицы. Конечно, можно заблаговременно составить список n для таких чисел. Но это значит, что список п для таких чисел нужно составить по другой программе, решающей фактически ту же задачу, решением которой мы сейчас как раз и заняты.

При решении этой вспомогательной задачи, правда, можно ограничиться перебором на меньших начальных отрезках натурального ряда. Конечно, этот способ решения вполне корректен. Но такой способ ведет к программе, которая выглядит несколько искусственно. Фактически получится не программа, а подглядывание в раздел ответов в случае небольших значений п. Ничего плохого в этом нет. Просто этот способ реализовать нельзя, если мы не знаем нужную нам часть ответа для решаемой задачи. Поэтому поступим иначе. Мы вообще сделаем вид, что не знаем даже начальных значений n. Сначала в программе найдем все те начальные значения n, при которых числа вида 5*2n +1не превосходят тех простых чисел q, которые использовались для построения таблицы. Хотя это и будет чистый перебор, перебирать придется недолго, поскольку числа вида 5*2n +1 с ростом и растут гораздо быстрее, чем и-е простое число рn. Например, если мы будем строить таблицу, используя первые 25 000 простых чисел, то перебирать без дополнительной отбраковки придется лишь первый десяток нечетных значений n. Затем можно будет построить таблицу и запустить процесс предварительной отбраковки.

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.