1940. Непростые годы

Задача заключается в нахождении простых чисел по версии капитана

задан 27 Янв '14 20:02

изменен 26 Май '14 21:25

Deleted's gravatar image


126

1

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

(27 Янв '14 20:59) falcao

@Falcao,я добавил ссылку вы говорили что у вас есть что-то новое по задаче

(28 Янв '14 20:12) ivan145

@ivan145: прежде чем написать здесь, я хотел немного поэкспериментировать с программами. В Maple я написал алгоритм в несколько строк, но это очень медленная система. Хочу сравнить с тем, как будет в Паскале. Там обычно всё существенно быстрее происходит. Постараюсь завтра всё описать (в принципе, я мог бы и сейчас это сделать, но лучше всё-таки после "прогона" программы).

(29 Янв '14 2:44) falcao

Пишу здесь,так как там занято.А дальше же написано,что берутся не все подмножества и описывается перебор с самого большого простого до k,там,вроде,тоже отсекаются варианты

(30 Янв '14 14:13) ivan145

@ivan145: я когда прочитал фразу "перебираем все подмножества", то дальше читать не стал. Сейчас я прочитал до конца, и стало понятно, что описывается та же самая процедура. НОК здесь совпадает с произведением, выбор знака плюс или минус определяется чётностью сомножителей. Разница только в том, что перебор начинается с деления на самые большие чисел, а не на маленькие. Но порядок разбора случаев не важен, так как сами случаи в точности те же. В общем, это эквивалентно тому, что я описывал в предыдущем обсуждении -- без учёта модификаций и улучшений.

(30 Янв '14 16:18) falcao

Falcao,ваш алгоритм со списками оказался правильным,т.е. тот который вы написали до этого.Получилось так,что на одном из компиляторов он проходил за 1.046,что больше секунды и не пролезало по ограничению по времени,но на другом компиляторе все это заняло 0.718.Алгоритм,который вы предложили во второй раз я не реализововал,но думаю он будет как минимум быстрее раза в два.Спасибо)

(31 Янв '14 17:47) ivan145

Можно ли вопрос закрыть,по причине того,что он отвечен

(31 Янв '14 22:34) ivan145

@ivan145: да, там есть в списке пункт типа "вопрос отвечен, и ответ принят". Только условие убирать не надо, потому что становится непонятно, на какой вопрос отвечали.

(1 Фев '14 2:41) falcao
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
2

Мне имело смысл "прогнать" программу при максимальных значениях, чтобы понять, какое число вариантов надо рассматривать при самом "грубом" способе перебора. Оно составляет где-то почти 6 миллионов, а это многовато. Тем не менее, если программа работает 3 секунды вместо требуемой одной, то алгоритм или его реализацию всегда можно слегка улучшить, не внося "радикальных" изменений.

Итак, я хочу начать с того, что при последовательных делениях на простые числа возникает определённое корневое дерево. Вверху находится число $%n$%. Из него идут вниз рёбра к вершинам $%[n/2]$%, $%[n/3]$%, $%[n/5]$%, ..., $%[n/p_m]$%. Число $%[n/2]$% мы далее делим с округлением на 3, 5, 7, 11, ..., и из него идут рёбра к соответствующим числам. И так на столько уровней вниз, пока числа после округлений остаются ненулевыми.

Строить полностью это дерево в процессе вычислений не требуется. Нам нужно всего лишь обходить каждую из его вершин в определённом порядке. Когда мы впервые посещаем очередную вершину, то к общей сумме мы прибавляем число $%\pm v$%, где $%v$% -- число, соответствующее данной вершине. Оно меняет знак с плюса на минус и обратно при спуске или поднятии на один уровень.

Запоминать в каждый текущий момент нам нужно только "ветку" дерева, ведущую из корня в просматриваемую вершину. Эта информация хранится в небольшом (менее 10 элементов) массиве. Вместе с числами (вершинами) в "параллельном" массиве мы запоминаем номер того простого числа, на который нам разрешено делить данное число $%v$%.

Покажем это на примере $%n=100$%, когда делить приходится на четыре простых числа: 2, 3, 5, 7. Хранимую информацию я буду записывать в виде пар (это как бы два массива). Начальная запись (100;1) означает, что рассматриваемся число 100, которое можно делить на самое первое простое число списка, то есть на два. Делаем это, и добавляем в массив пару (50;2). Теперь уже делить можно только на 3. Добавляем новую пару (16;3). Следующей будет (3;4). Здесь уже делить больше нельзя, поэтому возвращаемся назад. При этом нет необходимости менять массив, а достаточно иметь одну переменную (скажем, d), которая нам указывает номер просматриваемого элемента массива. Возврат назад означает выполнение команды d:=d-1, то есть мы переходим к паре (16;3), превращая её в (16;4), так как на третье простое число мы уже делили. Теперь после деления на 7 мы добавляем в массив пару (2;5), увеличивая d на 1, после чего идём назад (то есть d:=d-1). Это нас возвращает к (16;4), но 4 есть номер последнего простого числа. Снова делаем шаг назад (d:=d-1), и рассматриваем пару (50;2), превращая её в (50;3) и переходя от неё вниз к паре (10;4) после деления на 5. И так далее. Думаю, описываемый процесс ясен, равно как и то, какие слагаемые в его ходе добавляются к общей сумме.

Как я уже отмечал, для $%n$% порядка $%2\cdot10^9$% и для простых чисел в диапазоне 300, данное дерево имеет около $%6\cdot10^6$% вершин. Чтобы уменьшить это количество, увеличивая быстродействие программы в несколько раз, применим вот какое соображение.

Можно с самого начала отдельно учесть числа, делящиеся на 2 или на 3. Их количество на любом отрезке вычисляется по очень простой формуле. Всё, что туда не вошло, входит в одну из двух арифметических прогрессий: $%6k+1$% или $%6k+5$%. Каждую из прогрессий далее будем рассматривать по отдельности на предмет того, какие числа в ней делятся на 5, на 7, на 11, и так далее, и какие значения $%k$% этому соответствуют. Значения $%k$% при этом идут подряд, а диапазон для них сократится в 6 раз. Прогрессий две, то есть выигрыш во времени примерно втрое уже имеется. На самом деле, он будет существенно больше, так как при построении дерева делить надо будет только на простые числа, начиная с 5. Числа начинают убывать очень быстро, и число вершин дерева в размерах тоже уменьшается.

Последнее замечание касается подсчёта и суммирования. Допустим, нам надо понять, сколько членов прогрессии $%6k+5$% делится на, скажем, 17 при $%k$% от 2014 до 3000. Это несложная арифметическая задача: $%k$% должно при делении на 17 давать определённый остаток (в данном случае это 2), который в общем случае легко найти. И далее нужно подсчитать, сколько натуральных чисел удовлетворяет двойному неравенству $%2014\le17n+2\le3000$%, делается при помощи целочисленного деления.

Полагаю, что изложенного будет достаточно для того, чтобы уложиться в требуемое время. Расход памяти здесь совсем небольшой.

ссылка

отвечен 29 Янв '14 19:41

Можно с самого начала отдельно учесть числа, делящиеся на 2 или на 3. Их количество на любом отрезке вычисляется по очень простой формуле. Всё, что туда не вошло, входит в одну из двух арифметических прогрессий: 6k+1 или 6k+5. Каждую из прогрессий далее будем рассматривать по отдельности на предмет того, какие числа в ней делятся на 5, на 7, на 11, и так далее, и какие значения k этому соответствуют.Не совсем понимаю этот момент.Можно поподробней

(29 Янв '14 20:11) ivan145

У меня в тексте это далее разъясняется на примере делимости на 17. То есть, с моей точки зрения, я всё как бы предусмотрел и разъяснил. Если Вам что-то из сказанного не очевидно, я готов дать дополнительные пояснения, но я должен знать, на какие вещи надо обратить внимание.

(29 Янв '14 20:21) falcao

Допустим,мы учитываем числа делящиеся на 2.Посчитал их количество.Далее,вы говорите все,что туда не вошло входит в одну из арифметических прогрессий?Откуда взялись прогрессии?как понять все что туда не вошло?

(29 Янв '14 20:29) ivan145

А, то есть вопрос относился к прогрессиям? Это соображение я считал очевидным, поэтому детально не стал описывать. Все целые числа входят ровно в одну из шести последовательностей вида 6k+r, где r есть остаток от деления на 6, то есть в одну из прогрессий. Числа вида 6k, 6k+2, 6k+4 чётны. Числа вида 6k+3 кратны трём. Когда мы это всё учитываем и отбрасываем, то остаются числа двух оставшихся прогрессий, то есть как раз 6k+1 и 6k+5. В них входит всё то, что не делится ни на 2, ни на 3. Такой учёт полезно сделать в самом начале, чтобы "выловить" самое "крупное".

(29 Янв '14 20:38) falcao

Этот момент,теперь понятен.Далее я не понял почему остаток равен 2,и как с помощью целочисленного деления найти количество чисел,которые удовлетворяют этому неравенству

(29 Янв '14 21:02) ivan145

Остаток в рассмотренном мной примере равен 2, так как $%6\cdot2+5=17$%. Его значение находится подбором. По второму вопросу: мы имеем границы для $%17n+2$%. Вычитаем 2, делим на 17. Получается, что $%n$% лежит между $%2012/17$% и $%2998/17$%. Целые части этих чисел находятся при помощи операции div. А остальное, я надеюсь, очевидно. Например, неравенству $%118,3...\le n\le176,3...$% удовлетворяют числа от 119 до 176 включительно, и их имеется 58.

(29 Янв '14 21:54) falcao

На одном из форумов нашел следущее объяснение по этой задаче но не совсем его понял.Итак,что там говорят:Нас просят найти количество чисел от l до r, которые делятся на какое-то из первых k простых. Вообще, решение выглядит так: перебираем все подмножества из k элементов, смотрим, сколько чисел от l до r делятся на все числа из этого подмножества (то есть делятся на их НОК). Если подмножество было нечётной мощности, то прибавляем то количество к ответу, иначе вычитаем.

(30 Янв '14 9:41) ivan145

Продолжаю.Можно заметить, что для многих подмножеств их НОК будет больше 2·109 и они не дают никакой вклад в ответ. Чтобы их по максимуму отсекать мы реализуем перебор так: набираем числа в подмножество, проходя по массиву с конца (начиная с самого большого простого до k). Всё что нужно знать о подмножестве это: чётность его размера, последнее не рассмотренное число и его текущий НОК. Соответственно, мы либо берём первое не рассмотренное число в наше подмножество и пересчитаем ответ с учётом этого, либо не берём и передаём подмножество дальше, только уже с другим первым не рассмотренным числом

(30 Янв '14 9:42) ivan145

Как вы думаете,имеет ли это решение право на жизнь?И если да,не могли бы его объяснить поподробнее

(30 Янв '14 9:42) ivan145

@ivan145: это заведомо неприемлемый подход хотя бы по причине того, что подмножеств мощности $%k$% имеется очень и очень много. Даже если бы бы стали перебирать все пары (не говоря о подмножествах мощности 60), то их количество могло бы иметь порядок типа $%10^{18}$%, то есть миллиард миллиардов. Для сравнения: в столетии меньше 4 миллиардов секунд.

(30 Янв '14 11:05) falcao
показано 5 из 10 показать еще 5
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×4,844

задан
27 Янв '14 20:02

показан
1388 раз

обновлен
1 Фев '14 2:41

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru