3

Pythonでプロジェクトオイラーの問題3を解決しようとしています。

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

私のプログラムは非効率的で特大であることは知っていますが、なぜそれが機能しないのか知りたかっただけです。コードは次のとおりです。

def check(z):

# checks if the given integer is prime

    for i in range(2, z):
        if z % i == 0:
            return False
            break
        i = i+1
    return True

def primegen(y):
# generates a list of prime integers in the given range

    tab = []
    while y >= 2:
        if check(y) == True:
            tab.append(y)
        i = i-1


def mainfuntion(x):
# main function; prints the largest prime factor of the given integer

    primegen(x)
    for i in range(len(tab)):
        if x % tab[i] == 0:
            print tab[i]
            break

mainfuntion(600851475143)

そして、ここにエラーがあります：

for i in range(2, z):
OverflowError: range() result has too many items
4

4 に答える 4

11

その理由は、Pythonのリストが536,870,912要素に制限されており（Python配列が取得できる大きさを参照）、例で範囲を作成すると、要素の数がその数を超えてエラーが発生するためです。

Project Eulerの面白さは、自分で何かを理解することです（これは、あなたがやっていることを私は知っています:)）。そのため、そのエラーを回避する非常に小さなヒントを1つ挙げます。数値の因数が何であるかを考えてください。600851475142が600851475143の因数になることは不可能であることを知っています。したがって、その数値までずっとチェックする必要はありません。その論理に従って、チェックする範囲を大幅に減らす方法はありますか？素因数の性質について少し調べてみると、何か面白いものが見つかるかもしれません:)

于 2012-11-21T22:56:04.580 に答える
1

i = i+1まず、最初のコードブロックでは、forループが処理するため、使用しないでください。次に、xrangeリストの代わりにジェネレーターを作成するために使用します。

于 2012-11-21T23:07:14.830 に答える
1

これが私が使ったコードです!!

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

print n

-M1K3

于 2013-03-02T02:59:46.897 に答える
1

@ seamonkey8：コードを改善することができます。1つではなく2つ増やすことができます。非常に大きな数値の場合、速度に違いが生じます。

n,i = 6008514751231312143,2

while i*i <= n:      
    if n%i == 0:
        n //= i
    else: 
        i+=[1,2][i>2]
于 2014-12-13T16:47:51.303 に答える