素数の和で数値を表現

Python: represent a number as a sum of prime numbers – StackOverflow

任意の整数の組み合わせで任意の整数を表したい場合,
部分和問題でNP完全な問題になる.
以前のnumpyでブロードキャストを利用したのも部分和問題.

任意の整数を表す素数の組み合わせ全てだと,それよりも面倒な話.
結局,sympy.primerangeとisprimeを利用して総当りしか無いんだろうか.

ただ,これは最小長が欲しいだけなんだろうか.
だとすると,かなり簡単になる.

def p_minsum(x, cnt=0, res=None):
    if res is None:
        res = []
    cnt += 1
    for p in primerange(2, x//2):
        if isprime(x-p):
            cnt += 1
            res.extend([p, x-p])
            return cnt, res
    else:
        res.append(p)
        return p_minsum(x-p, cnt, res)

p_minsum(8)

(2,[3,5])

p_minsum(11)

(3,[3,3,5])

%timeit p_minsum(8)
%timeit p_minsum(9)
%timeit p_minsum(11)

28.7 µs ± 2.85 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
28.2 µs ± 2.33 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
53.7 µs ± 904 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

広告
カテゴリー: 未分類 パーマリンク

素数の和で数値を表現 への3件のフィードバック

  1. ピンバック: Maximum subarray problem | 粉末@それは風のように (日記)

  2. ピンバック: 部分集合和問題 | 粉末@それは風のように (日記)

  3. ピンバック: リスト内の整数ペア(2つの整数要素)の合計がターゲット値なればTrueを返す | 粉末@それは風のように (日記)

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中