-1

这是 Project Euler 的问题之一：

如果我们为 0 <= a <= 5 计算 a^2 mod 6，我们得到：0、1、4、3、4、1。

“a”的最大值使得 a^2 mod 6 = a 为 4。让我们称 M(n) 为 a < n 的最大值，使得 a^2 mod n = a。所以 M(6) = 4。

对于 1 <=n <=10^7 求 M(n)。

到目前为止，这就是我所拥有的：

import time
start = time.time()
from math import sqrt

squares=[]
for numba in xrange(0,10000001/2+2):
    squares.append(numba*numba)
def primes1(n):
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(sqrt(n))+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]


tot=0

gor = primes1(10000001)

def factor1(n):
    '''Returns whether a number has more than 1 prime factor'''
    boo = False


    '''if n in gor:
        return True'''


    for e in xrange(0,len(gor)):



        z=gor[e]    

        if n%z==0:

            if boo:
                return False
            boo = True
        elif z*2>n:  
            break
    return True

for n in xrange(2,10000001):

    if factor1(n):

        tot+=1
    else:
        for a in xrange(int(sqrt(n))+1,n/2+1):
            if squares[a]%n==a:

                tot+=n+1-a
                break

print tot
print time.time()-start

我已经在较小的情况下尝试了此代码，并且效果很好；但是，做 10^7 个案例太慢了。

目前，对于 n 小于 20000，它的运行时间约为 8 秒。当 n 小于 90000 时，它运行大约 150 秒。

据我所知，对于 n 小于 10^7，它会运行数小时甚至数天。

我已经在使用筛子生成素数，以便这部分尽可能快，我能做些什么来加快其余代码的速度吗？

我已经尝试过使用不同的编译器，例如 psyco、pypy 和 shedskin。Psyco 提供了最小的增加，shedskin 将其加速了大约 7 倍，但在出现大量数据时会产生错误，pypy 的速度最快（大约是速度的 20-30 倍）。但即便如此，对于必须处理的案件数量来说，它仍然不够快。

编辑：

我添加了

squares=[]
for numba in xrange(0,10000001/2+2):
    squares.append(numba*numba)

这会预先生成所有的正方形，a这样我就不必一遍又一遍地生成相同的正方形。程序变得稍快但仍然不够

4

1 回答 1

0

这可能取决于N内存使用的大小，但在较小的测试中，我通过预先计算因子计数发现了一些改进。所以是这样的：

factors = [0]*N
for z in gor:
  for n in xrange(1,N):
    m = z*n
    if m >= N: break
    factors[m] += 1

N10000001 或您使用的任何计数器在哪里。

然后代替if factor1(n)你做if factors[n] < 2。

于 2013-05-08T13:29:19.027 回答