Стоит ли запоминать тест на первичность?
У меня есть еще одна задача возврата, в которой я должен получить все возможные комбинации простых чисел, которые складываются до определенного числа. Я закончил задачу, используя алгоритм общего использования из Википедия, но для числа 100 потребовалось больше часа, и он все еще не закончил к концу урока. Мне было интересно: значительно ли запоминание (как это пишется?) Значительно улучшило производительность алгоритма (например, сделало бы оно заметно быстрее)? Я использую c ++, и функция вызывается огромное количество раз. Я использую рекурсивное отслеживание, которое, как мне кажется, я помню примерно как O (n!) Для простых задач.
Решение
Создайте массив, внешний по отношению к функции, проверяющий первичность и достижимый из нее. Глобальный или статический, в зависимости от используемого языка. Этот массив будет содержать все найденные первичные числа.
If the number in question is in the array, return true.
if number is less or equal than squared max number in the array, return false.
Check for divisibility for all known primaries
if the number is primary, write it into array and return true
return false
Это добавление достаточно просто. Сделайте это и проверьте измененное время.
Другие решения
Других решений пока нет …