| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск арифметических послед. из простых чисел |
| Автор: Rulikkk 28.9.2006, 15:37 |
| Доброго времени суток. Задача: Даны все простые числа 1 < (простые числа) < n n - большое, но не астрономическое (~10^9, например) Надо найти самую длинную арифметическую последовательность среди этих чисел. Ну то есть алгоритм придумать. ---------------------------------------- Что есть: 1. Придумал динамический алгоритм, по таблице где идут простые числа по вертикали и различные q по горизонтали - но это слишком много памяти, как оптимизировать не представляю. (ИМХО, это единственно верное рещение.) 2. Если m членов арифметической прогрессии являются простыми нечетными числами, то разность прогрессии делится на каждое простое число, меньшее m (В.Тебольт). Последовательность 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089 является арифметической прогрессией, состоящей из десяти возможно наименьших простых чисел. 3. Существует аналогичная прогрессия из 13 простых чисел: 4943, 65003, 125063, 185123, 245183, 305243, 365303, 425363, 485423, 545483, 605543, 665603, 725663. 4. Нашёл последовательность из 14. Начинается с 146141 с шагом 54444390. |
| Автор: ChVovan 30.9.2006, 18:43 |
| Задача по идее сводится к поиску всех простых меньших заданого n. После этого задача линейна. Где можно взять готовую таблицу простых чисел? |
| Автор: Akina 1.10.2006, 15:05 |
| таблица простых до 10^9? да сгенерируй - ей-бо, не на годы задача. Можно даже в лоб. |
| Автор: Rulikkk 2.10.2006, 15:09 |
| Сгенерировал. ДАЛЬШЕ ЧТО? |