Эта задача является первой из серии проблем с наименьшим количеством операций, которые должны быть записаны в ЦПУ GOLF . Вы можете найти следующий здесь
Разделение числа, N
это список чисел, которые складываются в N
. Простой раздел представляет собой список простых чисел , которые складываются в N
.
Для этого задания вам дается одно целое число N ≥ 2
. Вам нужно создать кратчайший из возможных простых разделов для N
. Если существует несколько возможных разделов, вы можете распечатать любой из них.
Примеры:
9: [2, 7]
12: [5, 7]
95: [89, 3, 3]
337: [337]
1023749: [1023733, 13, 3]
20831531: [20831323, 197, 11]
Ваша программа должна быть написана на GOLF CPU . Для ввода / вывода вы можете использовать либо STDIO, либо регистры. Список может быть в любом порядке и, если вы используете STDOUT, может быть разделен пробелами или запятыми (без скобок). Очевидно, что жесткое кодирование решений недопустимо, и при этом жесткое кодирование не является более простым, чем первые несколько простых чисел.
Это проблема с наименьшим количеством операций , поэтому ответ, который решает приведенные выше примеры с наименьшим количеством циклов, выигрывает!
источник
Ответы:
159 326 251 цикл
Ввод является
n
, выходr
,s
иt
(игнорируя нули).Testcases:
источник
Всего циклов для примеров: 477 918 603
Обновление 1: обновлено, чтобы использовать гипотезу Лемуана .
Обновление 2: Обновлено, чтобы использовать Сито Эратосфена вместо наивного поиска простых чисел.
Бежать с:
Пример выполнения:
Количество циклов для примера ввода:
Мы считаем первые
(N+1)*8
байты кучи массивом, содержащимN+1
64-битные значения. (Поскольку размер кучи ограничен, это будет работать только дляN < 2^57
). Значение записи вi*8
означает,i
является ли простое число:Когда мы закончим создание массива, он будет выглядеть следующим образом
[-1, -1, 3, 5, -1, 7, -1, 11, -1, -1, -1, 13, ...]
.Мы используем Сито Эратосфена для построения массива.
Далее программа выполняет следующие действия в псевдокоде:
Это гарантированно сработает из-за гипотезы Лемуана и слабой гипотезы Гольдбаха . Гипотеза Лемуана еще не доказана, но, вероятно, она верна для чисел ниже 2 ^ 57.
источник