День рождения Иванова(#1045) Бизнес-классики(#1047)

#1046

Задача g6_1046: Упаковка простых.

Михаил Густокашин, Евгений Бровкин

В первой строке входного файла input.txt дано число N (N <= 100) - количество пар значений min и max (999999 <= min < max <= 1250001). Требуется для каждой пары значений min и max найти количество простых чисел, лежащих в промежутке (min; max) и вывести их в соответствующую строку файла output.txt.
Оптимизировать программу по времени исполнения.
Пример входного файла:
3
999999 1250001
1000000 1000005
1234567 1250001
Пример выходного файла:
17971
1
1109

Решение g6_1046:
Как искать простые числа более или менее быстро я советую прочитать вам разбор задачи 1036 - Хитрющая строка.
Недаром задача названа "Упаковка простых". Если каждый раз идти от min до max и если разница между ними большая, то программа будет тормозить ужасно. Следовательно простые надо посчитать один раз и не пересчитывать позже. Т.е. воспользоваться методом динамического программирования. Если у вас FP/GNU C, то никаких проблем быть не должно, а вот если у вас BP/TP/BC, то придется применить хитрость, т.к. 17971 longint число в памяти укладываться не хочет. Здесь уместно использовать обобщенную теорему Евгения Бровкина о разнице между простыми числами. Теорема Евгения Бровкина гласит:

Разница между двумя последовательными простыми числами до 60000 простого числа не превышает 255

Обобщенная Михаилом Густокашиным теорема о разнице между простыми числами, гласит:

Разница между двумя последовательными простыми числами в промежутке от 1000000 до 1250000 не превышает 255

Значит уместно один раз посчитать разницу между последовательными простыми числами, а затем пользоваться ею. Это можно сделать двумя способами:

  • Считать каждый раз в начале работы программы
  • Посчитать один раз и занести как константу
    • Первым способ работает медленнее. Мы один раз пройдем от начала (999999) до конца (1250001) и будем при встрече простого числа записывать в очередной элемент массива разницу между этим числом и предыдущем. За первое число примем 1000000 - оно все равно не простое.
    Теперь идем по массиву с первого элемента и последовательно восстанавливаем простые числа. Если число больше min и меньше max, то увеличиваем счетчик на 1. При превышении max выводим счетчик и начинаем считать заново для новых min и max.

    Наверх