Разложение на простые числа

14

Получив целое число 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)

Это , поэтому выигрывает самый короткий ответ в байтах на каждом языке!

Изменить: теперь я знаю, почему я должен использовать песочницу в следующий раз

сфальсифицированы
источник
Связанные
Питер Тейлор

Ответы:

7

Haskell , 96 89 байт

5 байтов сохранено благодаря тесту первичности H.PWiz

p x=[1|0<-mod x<$>[2..x]]==[1]
f[]=1
f b=sum[f$drop i b|i<-[1..length b],p$read$take i b]

Попробуйте онлайн!

объяснение

Первое, что сделано, это создание простой тестовой функции с использованием теоремы Вильсона с использованием определения простого числа.

p x=[1|0<-mod x<$>[2..x]]==[1]

Тогда начните определять f. Первое, что я подумал, когда увидел эту проблему, это использование динамического программирования. Однако динамическое программирование стоит байтов, поэтому здесь используется алгоритм «псевдодинамического программирования». Принимая во внимание, что в динамическом программировании вы должны хранить ориентированный ациклический граф в памяти, здесь мы просто используем рекурсию и пересчитываем каждый узел каждый раз, когда нам это нужно. Он теряет все время преимущества динамического программирования, но это так кого это волнует. (все же лучше, чем поиск методом перебора)

Алгоритм заключается в следующем: мы строим направленный ациклический граф L , где каждый узел представляет подстроку числа. В частности, L i представляет последние i цифр нашего ввода (назовем это n ).

Мы определяем L 0, чтобы иметь значение 1, а каждое другое значение в L, чтобы иметь сумму каждого L j, такого, что j <i, и подстрока n от i до j является простой.

Или в формуле:

формула

Затем мы возвращаем значение на самом большом по величине индекса L . ( L k, где k - количество цифр n )

Пост Рок Гарф Хантер
источник
6

Желе , 8 байт

ŒṖḌÆPẠ€S

Попробуйте онлайн!

-1 байт благодаря Leaky Nun
-1 байт благодаря Деннису

объяснение

ŒṖḌÆPẠ€S  Main Link
ŒṖ        List Partitions (automatically converts number to decimal digits)
  Ḍ       Convert back to integers (auto-vectorization)
   ÆP     Are they primes? (auto-vectorization)
     Ạ€   For each, are they all truthy (were the numbers all primes?); 1/0 for truthy/falsy
       S  Sum; gets number of truthy elements
HyperNeutrino
источник
Я заметил, что 05AB1E не может сделать это легко. Перегородки кажутся отличной командой.
Волшебная Осьминог Урна
5

Брахилог , 10 байт

ṫ{~cịᵐṗᵐ}ᶜ

Попробуйте онлайн!

Сначала преобразует входные данные в строку. {…}ᶜПодсчитывает количество возможных выходов для .

Внутри {…}на выход подается ~c. Выходные данные этого предиката удовлетворяют тому, что при объединении он равен входным данным. Это вводится в ịᵐ, который указывает, что его вывод - это ввод с каждой строкой, преобразованной в целое число. ṗᵐуказывает, что его вход состоит из простых чисел

H.PWiz
источник
1
Вам не нужно преобразовать в строку и обратно, эти 7 байт достаточно: {~cṗᵐ}ᶜ. Это действительно медленно, потому что ~cна целых числах работает с арифметикой ограничения, но в теории это работает.
Роковая
@Fatalize Я думаю, что это не объясняет ведущие нули
H.PWiz
4

Pyth , 13 байт

lf.AmP_sdT./`

Тестирование.

Дрянная Монахиня
источник
Я не очень хорошо знаю Pyth, но вместо того, чтобы фильтровать и затем брать длину, вы могли бы сделать for_each вместо фильтра и затем суммировать?
HyperNeutrino
@HyperNeutrino это имеет какое-то значение?
Дрянная Монахиня
Я не уверен, я не проверял. Это относится к Jelly (возможно, из-за быстрого двухбайтового фильтра), но я не уверен.
HyperNeutrino
@HyperNeutrino фильтр один байт здесь ...
Leaky Nun
2

Python 2 , 161 байт

lambda n:sum(all(d>1and all(d%i>0for i in range(2,d))for d in v)for v in g(`n`))
g=lambda s:[[int(s[:i])]+t for i in range(1,len(s))for t in g(s[i:])]+[[int(s)]]

Попробуйте онлайн!

Функция gсоздает разделы рекурсивно (она принимает строку в качестве входных данных, но выводит список списков целых). Большая часть оставшегося кода просто для реализации « dпростое число?».

Час Браун
источник