Задача 50: Упаковка простых.
Михаил Густокашин,
Евгений Бровкин
В первой строке
входного файла 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
Решение:
Как искать простые числа более или менее быстро я советую прочитать
вам разбор задачи - Хитрющая строка.
Недаром задача названа "Упаковка простых". Если каждый раз идти от
min до max и если разница между ними большая, то программа будет
тормозить ужасно. Следовательно простые надо посчитать один раз и не
пересчитывать позже. Т.е. воспользоваться методом динамического
программирования. Если у вас FP/GNU C, то никаких проблем быть не
должно, а вот если у вас BP/TP/BC, то придется применить хитрость,
т.к. 17971 longint число в памяти укладываться не хочет. Здесь
уместно использовать обобщенную теорему Евгения Бровкина о разнице
между простыми числами. Теорема Евгения Бровкина гласит:
Разница между двумя последовательными простыми числами до 60000
простого числа не превышает 255
Обобщенная Михаилом Густокашиным теорема о разнице между простыми
числами, гласит:
Разница между двумя последовательными простыми числами в промежутке
от 1000000 до 1250000 не превышает 255
Значит уместно один раз посчитать разницу между последовательными
простыми числами, а затем пользоваться ею. Это можно сделать двумя
способами:
Считать каждый раз
в начале работы программы
Посчитать один раз
и занести как константу Первым способ работает медленнее. Мы один
раз пройдем от начала (999999) до конца (1250001) и будем при
встрече простого числа записывать в очередной элемент массива
разницу между этим числом и предыдущем. За первое число примем
1000000 - оно все равно не простое.
Теперь идем по массиву с первого элемента и последовательно
восстанавливаем простые числа. Если число больше min и меньше max,
то увеличиваем счетчик на 1. При превышении max выводим счетчик и
начинаем считать заново для новых min и max.
Далее
ð
