素数に分解する

整数 n が与えられた場合、nが素数のリストとして書き込まれる方法の数を返します。たとえば、
2323
(2,3,23)(23,23)または(2,3 、 4
を出力します。このように記述できない場合は、 0 を出力する必要があります。

01900000037
のような素数は、この問題の有効な素数です。

テストケース:

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)

This is ,
so the shortest answer in bytes in each language wins!

編集:今私はなぜ私はサンドボックスを次回使用すべきか知っています

ベストアンサー

Haskell, 96 89 bytes

H.PWizの素数性テストのおかげで5バイト保存

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]

Try it
online!

説明

最初に行われるのは、素数の定義を使ってウィルソンの定理を使って素数のテスト関数を作成することです。

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

Then begin defining f. The first thing I thought
when I saw this problem was to use dynamic programming. However
dynamic programming costs bytes so this uses a “psuedo-dynamic
programming” algorithm. Whereas in dynamic programming you would
store a Directed Acyclic graph in memory here we just use recursion
and recalculate each node every time we need it. It loses all of
the time benefits of dynamic programming, but this is so who
cares. (still better than brute force search though)

アルゴリズムは次のように、各ノードがその数の部分文字列を表す<�無限大> という有向無循環グラフを作成します。特に
L は入力の最後の i 桁を表します(それを
n と呼びます)。

We define L0 to have a value of 1
and each other value in L to have the sum of each
Lj such that j < i
and the substring of n from i to
j is prime.

または式で:

Formula

L の最大のインデックスに値を返します。 k
n の桁数です( L

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です