14

次の結果をもたらす効率的な Python イテレーター/ジェネレーターを構築したいと思います。

  • N 未満のすべての合成数
  • それらの素因数分解とともに

「composites_with_factors()」と呼びます

N 未満の素数のリスト、または同じことができる素数ジェネレーターが既にあると仮定します。

私が注意してください：

  • 数字が番号順に生成される必要はありません
  • 最初に 1 が返されるかどうかは気にしないでください
  • 素数が得られても気にしないでください

これは、巧妙な再帰ジェネレーターで実行できると思います...

たとえば、composites_with_factors(16) を呼び出すと、次のようになります。

# yields values in form of "composite_value, (factor_tuple)"
2, (2)
4, (2, 2)
8, (2, 2, 2)
6, (2, 3)
12, (2, 2, 3)
10, (2, 5)
14, (2, 7)
3, (3)
9, (3, 3)
15, (3, 5)
5, (5)
7, (7)
11, (11)
13, (13)

私の出力の順序からわかるように、利用可能な素数ジェネレーターで最小の素数から始めて、その素数の N 未満のすべての累乗を出力し、その素数の累乗を再試行することで、これが機能すると考えています。各段階で、追加の素数の累乗を適用できるかどうかを確認します (それでも N 未満です)。THAT 素数とのすべての組み合わせが完了したら、それをドロップし、素数ジェネレーターで利用可能な次に小さい素数で繰り返します。

「再帰ジェネレーター」を使用してこれを実行しようとすると、「yield」、「raise StopIteration」、または「return」を使用して再帰からいつ抜け出すか、または単純に再帰関数から抜け出すかについて、非常に混乱してしまいました。

あなたの知恵をありがとう！

追加の注意:

これを行う方法は 1 つあります。数値を因数分解する関数を作成したので、素数に因数分解して結果を得ることができます。問題ない。私は、「数 N の最小の素因数」のキャッシュに依存することで、これを非常に高速に保ちます... N は 1000 万までです。

しかし、いったんキャッシュから出てしまえば、それは「単純な」因数分解になります。（うん。）

この投稿のポイントは次のとおりです。

  • 「因子から大きな複合体を生成する」ことは、「大きな複合体を因子分解する」よりも高速であると想定しています...特に順序は気にしないので、
  • Python ジェネレーターを「再帰的に」呼び出して、生成されたものの単一のストリームを生成するにはどうすればよいですか?
4

3 に答える 3

10

primesiter(n)までのすべての素数に対して反復子を作成すると仮定しますn(1 を に含めないでくださいprimesiter。または、次のコードは inf. ループに入ります)。

def composite_value(n, min_p = 0):
    for p in primesiter(n):
        # avoid double solutions such as (6, [2,3]), and (6, [3,2])
        if p < min_p: continue
        yield (p, [p])
        for t, r in composite_value(n//p, min_p = p): # uses integer division
            yield (t*p, [p] + r)

出力

>> list(composite_value(16))
[(2, [2]),
 (4, [2, 2]),
 (8, [2, 2, 2]),
 (16, [2, 2, 2, 2]),
 (12, [2, 2, 3]),
 (6, [2, 3]),
 (10, [2, 5]),
 (14, [2, 7]),
 (3, [3]),
 (9, [3, 3]),
 (15, [3, 5]),
 (5, [5]),
 (7, [7]),
 (11, [11]),
 (13, [13])]

注: n (= 16) も含まれており、タプルの代わりにリストを使用しました。どちらも必要に応じて簡単に解決できますが、演習として残します。

于 2012-04-11T16:26:17.727 に答える
4

これはふるいベースの実装です（非Pythonicコードを許してください:)）：

def sieve(n):
    # start each number off with an empty list of factors
    #   note that nums[n] will give the factors of n
    nums = [[] for x in range(n)]
    # start the counter at the first prime
    prime = 2
    while prime < n:
        power = prime
        while power < n:
            multiple = power
            while multiple < n:
                nums[multiple].append(prime)
                multiple += power
            power *= prime
        # find the next prime
        #   the next number with no factors
        k = prime + 1
        if k >= n:    # no primes left!!!
            return nums
        # the prime will have an empty list of factors
        while len(nums[k]) > 0:
            k += 1
            if k >= n:    # no primes left!!!
                return nums
        prime = k
    return nums


def runTests():
    primes = sieve(100)
    if primes[3] == [3]:
        print "passed"
    else:
        print "failed"
    if primes[10] == [2,5]:
        print "passed"
    else:
        print "failed"
    if primes[32] == [2,2,2,2,2]:
        print "passed"
    else:
        print "failed"

テスト:

>>> runTests()
passed
passed
passed

私のマシンでは、これを実行するのに 56 秒かかりました。

primes = sieve(14000000) # 14 million!

例:

>>> primes[:10]
[[], [], [2], [3], [2, 2], [5], [2, 3], [7], [2, 2, 2], [3, 3]]

>>> primes[10000]
[2, 2, 2, 2, 5, 5, 5, 5]

>>> primes[65536]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

>>> primes[6561]
[3, 3, 3, 3, 3, 3, 3, 3]

>>> primes[233223]
[3, 17, 17, 269]

メモリ消費量: 約 5,000 万個の整数、1,400 万個のリスト:

>>> sum(map(len, primes))
53303934
于 2012-04-11T16:45:04.857 に答える
0

再帰的に (疑似コード):

def get_factorizations_of_all_numbers( start = starting_point
                                     , end = end_point
                                     , minp = mimimum_prime
                                     ):
    if start > end:
        return Empty_List
    if minp ^ 2 > end:
        return list_of_all_primes( start, end )
    else
        a = minp * get_factorizations_of_all_numbers( rounddown(start/minp)
                                                    , roundup(end/minp)
                                                    )
        b = get_factorizations_of_all_numbers( start
                                             , end
                                             , next_prime( minp )
                                             )
        return append( a , b )

get_factorizations_of_all_numbers( 1, n, 2 )
于 2012-04-11T16:42:00.253 に答える