打开与程序相关的文件是否也会停止程序？

Question

我有这个程序,应该搜索完美的数字.(如果除以X的所有数的总和等于X,则X是一个完美的数)
sum/2 = x

现在已经找到了前四个,这在古希腊是众所周知的,所以它并不是真的有点令人敬畏.

下一个应该是33550336.

我知道这是一个很大的数字,但该程序已经持续了大约50分钟,仍然没有找到33550336.

是因为我打开了.txt文件,我在程序运行时存储了所有完美的数字,还是因为我没有足够快的PC运行它*,或者因为我使用的是Python？

*注意:同样的PC在10分钟内分解了50万(同时还运行了完美的数字程序和带有3个YouTube标签的谷歌浏览器),也使用了Python.

这是程序的代码:

i = 2
a = open("perfect.txt", 'w')
a.close()
while True:
    sum = 0
for x in range(1, i+1):
    if i%x == 0:
        sum += x
if sum / 2 == i:
    a = open("perfect.txt", 'a')
    a.write(str(i) + "\n")
    a.close()
i += 1

Answer 1

下一个应该是33550336.

你的代码(我修改了缩进,以便原则上你想要的):

i = 2
a = open("perfect.txt", 'w')
a.close()
while True:
    sum = 0
    for x in range(1, i+1):
        if i%x == 0:
            sum += x
    if sum / 2 == i:
        a = open("perfect.txt", 'a')
        a.write(str(i) + "\n")
        a.close()
    i += 1

的确i部门发现的约数i.

所以要找到最完美的数字n,它确实如此

2 + 3 + 4 + ... + (n-1) + n = n*(n+1)/2 - 1

for循环中的分裂.

现在,因为n = 33550336,那将是

Prelude> 33550336 * (33550336 + 1) `quot` 2 - 1
562812539631615

大约5.6*10 ^14个分区.

假设您的CPU 每秒可以执行10 ^9个分区(很可能不会,10 ⁸在我的经验中是更好的估计,但即使是int在C中的机器),也需要大约560,000秒.一天有86400秒,所以这将是大约六天半(超过两个月,估计10 ⁸).

您的算法太慢,无法在合理的时间内达到该算法.

如果你不想使用数论(即使完美的数字有一个非常简单的结构,如果有任何奇数的完美数字,那些必然是巨大的),你仍然可以通过仅除以平方根来做得更好找到除数,

i = 2
a = open("perfect.txt", 'w')
a.close()
while True:
    sum = 1
    root = int(i**0.5)
    for x in range(2, root+1):
        if i%x == 0:
            sum += x + i/x
    if i == root*root:
        sum -= x        # if i is a square, we have counted the square root twice
    if sum == i:
        a = open("perfect.txt", 'a')
        a.write(str(i) + "\n")
        a.close()
    i += 1

只需要大约1.3*10 ^11个分区,并且应该在几个小时内找到第五个完美数字.

如果不使用明确的公式来表示即使是完美的数字(2^(p-1) * (2^p - 1)对于素数p这样2^p - 1的素数),也可以通过找到素数因子i并从中计算除数和来加速它.这将使所有复合数字的测试更快,对大多数人来说更快,

def factorisation(n):
    facts = []
    multiplicity = 0
    while n%2 == 0:
        multiplicity += 1
        n = n // 2
    if multiplicity > 0:
        facts.append((2,multiplicity))
    d = 3
    while d*d <= n:
        if n % d == 0:
            multiplicity = 0
            while n % d == 0:
                multiplicity += 1
                n = n // d
            facts.append((d,multiplicity))
        d += 2
    if n > 1:
        facts.append((n,1))
    return facts

def divisorSum(n):
    f = factorisation(n)
    sum = 1
    for (p,e) in f:
        sum *= (p**(e+1) - 1)/(p-1)
    return sum

def isPerfect(n):
    return divisorSum(n) == 2*n

i = 2
count = 0
out = 10000
while count < 5:
    if isPerfect(i):
        print i
        count += 1
    if i == out:
        print "At",i
        out *= 5
    i += 1

在我的机器上估计需要40分钟.

估计不错:

$ time python fastperf.py 
6
28
496
8128
33550336

real    36m4.595s
user    36m2.001s
sys     0m0.453s