3

オイラー問題 12に苦労しています。そこにたどり着くための答えや正確なコード変更は必要ありません。私はただ正しい方向に向けられることを望んでいます。このコードを約 10 分間実行したところ、正しくない回答が得られました。これにより、500 を超える約数の三角形数には 10000 を超える因数がないという私の仮定は正しくないと信じるようになります。私は、より高速な素数ジェネレーターを使用し、プログラムがリストを繰り返し処理するのをやめさせる必要があると考えています。後者を行う方法がわかりません。

def eratosthenes_sieve(limit):
    primes = {}
    listofprimes = []
    for i in range(2, limit + 1):
        primes[i] = True

    for i in primes:
        factors = range(i, limit + 1, i)
        for f in factors[1:limit + 1]:
            primes[f] = False

    for i in primes:
        if primes[i] == True:
            listofprimes.append(i)
    return listofprimes


def prime_factorization(n):
    global primal
    prime_factors = {}
    for i in primal:
        if n < i:
            i = primal[0]
        if n % i == 0:
            if i not in prime_factors.keys():
                prime_factors[i] = 1
            else:
                prime_factors[i] += 1
            n = n / i
        if n in primal:
            if n not in prime_factors.keys():
                prime_factors[n] = 1
            else:
                prime_factors[n] += 1
            return prime_factors
    return prime_factors    

def divisor_function(input):
    x = 1
    for exp in input.values():
        x *= exp + 1
    return x

def triangle(th):
    terms = []
    for each in range(1, th+1):
        terms.append(each)
    return sum(terms)

z = 1
primal = eratosthenes_sieve(10000)
found = False
while found == False:
triz = triangle(z)
number_of_divisors = divisor_function(prime_factorization(triz))

if number_of_divisors > 300:
    print "GETTING CLOSE!! ********************************"
if number_of_divisors > 400:
    print "SUPER DUPER CLOSE!!! *********************************************************"
if number_of_divisors < 501:
    print "Nope. Not %s...Only has %s divisors." % (triz, number_of_divisors)

    z += 1
else:
    found = True
    print "We found it!"
    print "The first triangle number with over 500 divisors is %s!" % triangle(z)
4

1 に答える 1

1

もちろん、投稿して数分でわかります。

私のprime_factorization関数で。

n％i == 0の場合：n％i==0の間にあるはずです。

そのため、プログラムは要素を見逃し、素数のリスト全体を実行していました。

于 2013-02-28T22:01:56.963 に答える