python - Python 素因数の検索

Question

2 つの部分からなる質問:

600851475143 の最大の素因数を決定しようとして、このプログラムがオンラインで動作するように見えることを発見しました。問題は、プログラムが何をしているかの基本は理解していますが、それがどのように機能するかを正確に理解するのに苦労していることです。また、おそらくすべての数をテストせずに素因数を見つける方法と、その方法がどのように機能するかについて、あなたが知っている可能性のある方法に光を当てることができれば幸いです.

素因数分解のためにオンラインで見つけたコードは次のとおりです [注: このコードは正しくありません。より良いコードについては、以下の Stefan の回答を参照してください。] :

n = 600851475143
i = 2
while i * i < n:
     while n % i == 0:
         n = n / i
     i = i + 1

print(n)

#takes about ~0.01secs

速度をテストするだけで、それ以外の目的がないこのコードよりも、そのコードの方がはるかに高速なのはなぜですか?

i = 1 while i < 100: i += 1 #約 3 秒かかります

score 98 · Accepted Answer

この質問は、私がググったときにポップアップした最初のリンクでした"python prime factorization"。@ quangpn88 によって指摘されたように、このアルゴリズムは次のような完全な平方に対しては間違っています (!)。n = 4, 9, 16, ...ただし、@ quangpn88 の修正も機能しませn = 2*2*2 = 8んn = 2*3*3*3 = 54。

Python の正しいブルートフォースアルゴリズムは次のとおりだと思います。

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

これをパフォーマンスコードで使用しないでください。

In [1]: %timeit largest_prime_factor(600851475143)
1000 loops, best of 3: 388 µs per loop

完全な素因数分解が求められる場合、これは力ずくのアルゴリズムです。

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

score 43 · Accepted Answer

Ok。つまり、基本は理解していると言いましたが、それがどのように機能するのか正確にはわかりません。まず第一に、これは Project Euler の質問に対する素晴らしい回答です。私はこの問題について多くの調査を行ってきましたが、これが最も単純な回答です。

説明のため、とさせていただきますn = 20。実際の Project Euler 問題を実行するには、n = 600851475143.

n = 20 
i = 2

while i * i < n:
    while n%i == 0:
        n = n / i
    i = i + 1

print (n)

この説明では、2 つのwhileループを使用します。ループについて覚えておくべき最大のことwhileは、ループがなくなるまで実行されることtrueです。

外側のループは、 whilei * iがより大きくないn(最大の素因数がの平方根より大きくなることはないため) と述べており、内側のループの実行後にnを追加1します。i

内側のループは、 while をiに均等に分割し、をで割ったものnに置き換えることを示しています。このループは、真でなくなるまで継続的に実行されます。とがに置き換えられ、次に再びに置き換えられます。はに均等に分割されないため、でループが停止し、外側のループが終了してが生成されます。nnin=20i=2n10525n=5i+1=3

最後に、3squared はより大きいため5、外側のループはもはやではなくtrue、の結果を出力しnます。

これを投稿してくれてありがとう。コードが正確にどのように機能するかを理解する前に、コードを永遠に見ました。うまくいけば、これが応答で探しているものです。そうでない場合はお知らせください。詳しく説明します。

score 18 · Accepted Answer

素数の生成には、常にエラトステネスのふるいを使用します。

def primes(n):
    if n<=2:
        return []
    sieve=[True]*(n+1)
    for x in range(3,int(n**0.5)+1,2):
        for y in range(3,(n//x)+1,2):
            sieve[(x*y)]=False
         
    return [2]+[i for i in range(3,n,2) if sieve[i]]

In [42]: %timeit primes(10**5)
10 loops, best of 3: 60.4 ms per loop

In [43]: %timeit primes(10**6)
1 loops, best of 3: 1.01 s per loop

Miller-Rabin primality testを使用して、数値が素数かどうかを確認できます。Python の実装はこちらで確認できます。

常にtimeitモジュールを使用してコードの時間を計ります。2 番目のものは次のようになります15us。

def func():
    n = 600851475143
    i = 2
    while i * i < n:
         while n % i == 0:
            n = n / i
         i = i + 1

In [19]: %timeit func()
1000 loops, best of 3: 1.35 ms per loop

def func():
    i=1
    while i<100:i+=1
   ....:     

In [21]: %timeit func()
10000 loops, best of 3: 15.3 us per loop

score 6 · Accepted Answer

これを行う別の方法：

import sys
n = int(sys.argv[1])
result = []
for i in xrange(2,n):
    while n % i == 0:
        #print i,"|",n
        n = n/i
        result.append(i)

    if n == 1: 
        break

if n > 1: result.append(n)
print result

出力例:
python test.py 68
[2, 2, 17]

score 5 · Accepted Answer

コードは 100 で間違っています。ケース i * i = n をチェックする必要があります。

私はそれがあるべきだと思います：

while i * i <= n:
    if i * i = n:
        n = i
        break

    while n%i == 0:
        n = n / i
    i = i + 1

print (n)

score 0 · Accepted Answer

昔ながらのナイスな方法でこれをハッキングしようとしている人は誰もいないのでreduce、私はこの仕事を引き受けます。このメソッドは、引数の配列に対して繰り返されるアクションのループを実行し、デフォルトではこのループを中断する方法がないため、このような問題には柔軟ではありません。interupted reduce次のように独自の for interrupted ループを実装すると、ドアが開きます。

from functools import reduce

def inner_func(func, cond, x, y):
    res = func(x, y)
    if not cond(res):
        raise StopIteration(x, y)
    return res

def ireducewhile(func, cond, iterable):
    # generates intermediary results of args while reducing
    iterable = iter(iterable)
    x = next(iterable)
    yield x
    for y in iterable:
        try:
            x = inner_func(func, cond, x, y)
        except StopIteration:
            break
        yield x

その後、標準の Python reduce メソッドfuncの入力と同じものを使用できるようになります。これを次のように定義します。func

def division(c):
    num, start = c
    for i in range(start, int(num**0.5)+1):
        if num % i == 0:
            return (num//i, i)
    return None

数値 600851475143 を因数分解したいと仮定すると、この関数を繰り返し使用した後のこの関数の期待される出力は次のようになります。

(600851475143, 2) -> (8462696833 -> 71), (10086647 -> 839), (6857, 1471) -> None

タプルの最初の項目は、divisionメソッドが取り、2 番目の項目から始まり、この数値の平方根で終わる最小の除数で割ろうとする数値です。除数が存在しない場合は、None が返されます。次に、次のように定義されたイテレータから始める必要があります。

def gener(prime):
    # returns and infinite generator (600851475143, 2), 0, 0, 0...
    yield (prime, 2)
    while True:
        yield 0

最後に、ループの結果は次のとおりです。

result = list(ireducewhile(lambda x,y: div(x), lambda x: x is not None, iterable=gen(600851475143)))
#result: [(600851475143, 2), (8462696833, 71), (10086647, 839), (6857, 1471)]

また、素因数の出力は次のようにキャプチャできます。

if len(result) == 1: output = result[0][0]
else: output = list(map(lambda x: x[1], result[1:]))+[result[-1][0]]
#output: [2, 71, 839, 1471]

ノート：

より効率的にするために、この範囲のすべての値ではなく、特定の範囲にある事前生成された素数を使用することができます。

score -1 · Accepted Answer

数値の平方根までループするべきではありません! 場合によっては正しい場合もありますが、常にそうとは限りません。

10 の最大の素因数は 5 で、sqrt(10) (3.16、約) よりも大きくなります。

33 の最大の素因数は 11 で、sqrt(33) よりも大きい (5.5,74、約)。

あなたはこれを、ある数がその平方根よりも大きな素因数を持っている場合、その平方根よりも小さい別の素因数を少なくとももう 1 つ持つ必要があるという妥当性と混同しています。したがって、数値が素数であるかどうかをテストしたい場合は、平方根までテストするだけで済みます。

python - Python 素因数の検索

20 に答える 20

ノート：

Related

Reference