Получив целое число n
, верните количество способов, которыми n может быть записано в виде списка простых чисел. Например, 2323
можно записать как (2,3,23)
, (23,23)
или (2,3,2,3)
или (23,2,3)
, так что вы бы вывести 4
. Если это не может быть написано таким образом, вы должны вывести 0
.
Простое число, такое как 019
или 00000037
является допустимым простым числом для этой задачи.
Тестовые случаи:
5 -> 1
55 -> 1
3593 -> 4 (359 and 3, or 3 and 593, or 3 and 59 and 3, or 3593)
3079 -> 2 (3 and 079, or 3079)
119 -> 0
5730000037 -> 7 (5,7,3,000003,7, 5,7,3,0000037, 5,73,000003,7, 5,73,0000037, 5,73000003,7, 5,7,30000037, 5730000037)
0-> undefined (you do not have to handle this case)
Это код-гольф , поэтому выигрывает самый короткий ответ в байтах на каждом языке!
Изменить: теперь я знаю, почему я должен использовать песочницу в следующий раз
code-golf
math
primes
set-partitions
сфальсифицированы
источник
источник
Ответы:
Haskell ,
9689 байт5 байтов сохранено благодаря тесту первичности H.PWiz
Попробуйте онлайн!
объяснение
Первое, что сделано, это создание простой тестовой функции
с использованием теоремы Вильсона сиспользованием определения простого числа.Тогда начните определять
f
. Первое, что я подумал, когда увидел эту проблему, это использование динамического программирования. Однако динамическое программирование стоит байтов, поэтому здесь используется алгоритм «псевдодинамического программирования». Принимая во внимание, что в динамическом программировании вы должны хранить ориентированный ациклический граф в памяти, здесь мы просто используем рекурсию и пересчитываем каждый узел каждый раз, когда нам это нужно. Он теряет все время преимущества динамического программирования, но это код-гольф, так кого это волнует. (все же лучше, чем поиск методом перебора)Алгоритм заключается в следующем: мы строим направленный ациклический граф L , где каждый узел представляет подстроку числа. В частности, L i представляет последние i цифр нашего ввода (назовем это n ).
Мы определяем L 0, чтобы иметь значение 1, а каждое другое значение в L, чтобы иметь сумму каждого L j, такого, что j <i, и подстрока n от i до j является простой.
Или в формуле:
Затем мы возвращаем значение на самом большом по величине индекса L . ( L k, где k - количество цифр n )
источник
Желе , 8 байт
Попробуйте онлайн!
-1 байт благодаря Leaky Nun
-1 байт благодаря Деннису
объяснение
источник
Брахилог , 10 байт
Попробуйте онлайн!
Сначала
ṫ
преобразует входные данные в строку.{…}ᶜ
Подсчитывает количество возможных выходов для…
.Внутри
{…}
на выходṫ
подается~c
. Выходные данные этого предиката удовлетворяют тому, что при объединении он равен входным данным. Это вводится вịᵐ
, который указывает, что его вывод - это ввод с каждой строкой, преобразованной в целое число.ṗᵐ
указывает, что его вход состоит из простых чиселисточник
{~cṗᵐ}ᶜ
. Это действительно медленно, потому что~c
на целых числах работает с арифметикой ограничения, но в теории это работает.Pyth , 13 байт
Тестирование.
источник
Python 2 ,
1059591 байтЭто очень медленно.
Попробуйте онлайн!
источник
Python 2 , 161 байт
Попробуйте онлайн!
Функция
g
создает разделы рекурсивно (она принимает строку в качестве входных данных, но выводит список списков целых). Большая часть оставшегося кода просто для реализации «d
простое число?».источник
Gaia , 12 байт
Попробуйте онлайн!
источник
Чистый ,
199141131 байтПопробуйте онлайн!
источник
J ,
6564 байтаПопробуйте онлайн!
источник
Pyth, 12 байт
Принимает ввод как целое число, выводит
True
илиFalse
Попробуйте онлайн!
источник