4

我有以下项目欧拉问题 12 的代码。但是，执行需要很长时间。有人对加快速度有什么建议吗？

n = input("Enter number: ")
def genfact(n):
    t = []
    for i in xrange(1, n+1):
        if n%i == 0:
            t.append(i)
    return t

print "Numbers of divisors: ", len(genfact(n))
print

m = input("Enter the number of triangle numbers to check: ")
print
for i in xrange (2, m+2):
    a = sum(xrange(i))
    b = len(genfact(a))
    if b > 500:
        print a

对于 n，我输入一个任意数字，例如 6，只是为了检查它是否确实返回了因子数列表的长度。对于 m，我输入 80 000 000

它适用于小数字相对较快。如果我输入b > 50；它为 a 返回 28，这是正确的。

4

5 回答 5

4

我在这里的回答既不漂亮也不优雅，它仍然是蛮力。但是，它稍微简化了问题空间，并在不到 10 秒的时间内成功终止。

获取 n 的因子： 就像提到的 @usethedeathstar 一样，可以测试仅高达n/2. 但是，我们可以通过只测试 n 的平方根来做得更好：

let n = 36
=> factors(n) : (1x36, 2x18, 3x12, 4x9, 6x6, 9x4, 12x3, 18x2, 36x1)

如您所见，它在 6（36 的平方根）之后循环。我们也不需要显式返回因子，只需找出有多少......所以只需使用 sum() 内部的生成器计算它们：

import math

def get_factors(n):
    return sum(2 for i in range(1, round(math.sqrt(n)+1)) if not n % i)

测试三角数

我使用了生成器函数来产生三角数：

def generate_triangles(limit):
    l = 1
    while l <= limit:
        yield sum(range(l + 1))
        l += 1

最后，开始测试：

def test_triangles():
    triangles = generate_triangles(100000)
    for i in triangles:
        if get_factors(i) > 499:
            return i

使用分析器运行它，它在不到 10 秒内完成：

$ python3 -m cProfile euler12.py 

361986 function calls in 8.006 seconds

这里最大的节省时间是get_factors(n)只测试 n 的平方根 - 这使它更快，并且通过不生成因子列表来节省大量内存开销。

正如我所说，它仍然不漂亮——我相信还有更优雅的解决方案。但是，它符合更快的要求:)

于 2013-07-19T11:41:09.107 回答
4

I got my answer to run in 1.8 seconds with Python.

import time
from math import sqrt


def count_divisors(n):
    d = {}
    count = 1

    while n % 2 == 0:
        n = n / 2
        try:
            d[2] += 1
        except KeyError:
            d[2] = 1

    for i in range(3, int(sqrt(n+1)), 2):
        while n % i == 0 and i != n:
            n = n / i
            try:
                d[i] += 1
            except KeyError:
                d[i] = 1

    d[n] = 1

    for _,v in d.items():
        count = count * (v + 1)

    return count

def tri_number(num):
  next = 1 + int(sqrt(1+(8 * num)))
  return num + (next/2)


def main():
    i = 1
    while count_divisors(i) < 500:
        i = tri_number(i)
    return i


start = time.time()
answer = main()
elapsed = (time.time() - start)

print("result %s returned in %s seconds." % (answer, elapsed))

Here is the output showing the timedelta and correct answer:

$ python ./project012.py
result 76576500 returned in 1.82238006592 seconds.

Factoring

For counting the divisors, I start by initializing an empty dictionary and a counter. For each factor found, I create key of d[factor] with value of 1 if it does not exist, otherwise, I increment the value d[factor].

For example, if we counted the factors 100, we would see d = {25: 1, 2: 2}

The first while loop, I factor out all 2's, dividing n by 2 each time. Next, I begin factoring at 3, skipping two each time (since we factored all even numbers already), and stopping once I get to the square root of n+1.

We stop at the square_root of n because if there's a pair of factors with one of the numbers bigger than square_root of n, the other of the pair has to be less than 10. If the smaller one doesn't exist, there is no matching larger factor. https://math.stackexchange.com/questions/1343171/why-only-square-root-approach-to-check-number-is-prime

while n % 2 == 0:
        n = n / 2
        try:
            d[2] += 1
        except KeyError:
            d[2] = 1

    for i in range(3, int(sqrt(n+1)), 2):
        while n % i == 0 and i != n:
            n = n / i
            try:
                d[i] += 1
            except KeyError:
                d[i] = 1
d[n] = 1

Now that I have gotten each factor, and added it to the dictionary, we have to add the last factor (which is just n).

Counting Divisors

Now that the dictionary is complete, we loop through each of the items, and apply the following formula: d(n)=(a+1)(b+1)(c+1)... https://www.wikihow.com/Determine-the-Number-of-Divisors-of-an-Integer

All this formula means is taking all of the counts of each factor, adding 1, then multiplying them together. Take 100 for example, which has factors 25, 2, and 2. We would calculate d(n)=(a+1)(b+1) = (1+1)(2+1) = (2)(3) = 6 total divisors

for _,v in d.items():
    count = count * (v + 1)

return count

Calculate Triangle Numbers

Now, taking a look at tri_number(), you can see that I opted to calculate the next triangle number in a sequence without manually adding each whole number together (saving me millions of operations). Instead I used T(n) = n (n+1) / 2 http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/runsums/triNbProof.html

We are providing a whole number to the function as an argument, so we need to solve for n, which is going to be the whole number to add next. Once we have the next number (n), we simply add that single number to num and return

S=n(n+1)2

S=n2+n2

2S=n2+n

n2+n−2S=0

At this point, we use the quadratic formula for : ax2+bx+c=0.

n=−b±√b2−4ac / 2a

n=−1±√1−4(1)(−2S) / 2

n=−1±√1+8S / 2

https://socratic.org/questions/how-do-you-solve-for-n-in-s-n-n-1-2

So all tri_number() does is evaluate n=1+√1+8S / 2 (we ignore the negative equation here). The answer that is returned is the next triangle number in the sequence.

def tri_number(num):
  next = 1 + int(sqrt(1+(8 * num)))
  return num + (next/2)

Main Loop

Finally, we can look at main(). We start at whole number 1. We count the divisor of 1. If it is less than 500, we get the next triangle number, then try again and again until we get a number with > 500 divisors.

def main():
    i = 1
    while count_divisors(i) < 500:
        i = tri_number(i)
    return i

I am sure there are additional ways to optimize but I am not smart enough to understand those ways. If you find any better ways to optimize python, let me know! I originally solved project 12 in Golang, and that run in 25 milliseconds!

$ go run project012.go
76576500
2018/07/12 01:56:31 TIME: main() took 23.581558ms
于 2018-07-12T07:06:13.227 回答
0

我可以给出的提示之一是

def genfact(n):
    t = []
    for i in xrange(1, n+1):
        if n%i == 0:
            t.append(i)
    return t

将其更改为

def genfact(n):
    t=[]
    for i in xrange(1,numpy.sqrt(n)+1):
        if(n%i==0):
           t.append(i)
           t.apend(n/i)

因为如果a是除数，那么b = n / a也是如此，因为a * b = a * n / b = n，那应该已经对一部分有所帮助（不确定在您的情况下是否可以使用正方形，但是如果是这样，添加另一种情况以排除两次添加相同的数字）

你也可以设计一个递归的东西，（比如如果它是类似 28 的东西，你得到 1,28,2,14 并且在你知道 14 的那一刻，你输入一些东西来实际记住 14 的除数（memoize )，而不是检查它们是否已经在列表中，如果没有，将它们添加到列表中，以及 14 的每个除数的 28/d，最后只需取出重复项

如果您认为我的第一个答案仍然不够快，请要求更多，我会检查如何通过更多技巧更快地解决它（可能也可以使用erastothenes sieve左右，还有一些其他技巧可以如果您希望真正将问题放大到很大的比例，也可以考虑一下，例如检查第一个除数超过 10k 左右的问题）

于 2013-07-19T10:45:30.770 回答
0 
while True:
    c=0
    n=1
    m=1
    for i in range(1,n+1):
        if n%i==0:
            c=c+1
            m=m+1    
            n=m*(m+1)/2
            if c>500:
                break
print n
于 2016-04-30T15:42:51.970 回答
0

这不是我的代码，但它是如此优化。来源：http ://code.jasonbhill.com/sage/project-euler-problem-12/

import time


def num_divisors(n):
    if n % 2 == 0: n = n / 2
    divisors = 1
    count = 0
    while n % 2 == 0:
        count += 1
        n = n / 2
    divisors = divisors * (count + 1)
    p = 3
    while n != 1:
        count = 0
        while n % p == 0:
            count += 1
            n = n / p
        divisors = divisors * (count + 1)
        p += 2
    return divisors


def find_triangular_index(factor_limit):
    n = 1
    lnum, rnum = num_divisors(n), num_divisors(n + 1)
    while lnum * rnum < 500:
        n += 1
        lnum, rnum = rnum, num_divisors(n + 1)
    return n


start = time.time()
index = find_triangular_index(500)
triangle = (index * (index + 1)) / 2
elapsed = (time.time() - start)

print("result %s returned in %s seconds." % (triangle, elapsed))
于 2018-06-22T12:32:33.803 回答