可以表示为两个数 x 和 y 平方和的质数

Question

问题是：

给定一个数字范围 (x,y)，找出所有的质数（只计算数量），这些质数是两个数字平方和的结果，条件是 0<=x<y<=2*(10^8)。

根据费马定理：

Fermat's theorem on sums of two squares asserts that an odd prime number p can be   
expressed as p = x^2 + y^2 with integer x and y if and only if p is congruent to 
1 (mod4).

我做过类似的事情：

import math
def is_prime(n):
    if n % 2 == 0 and n > 2:
        return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))

a,b=map(int,raw_input().split())
count=0
for i in range(a,b+1):
    if(is_prime(i) and (i-1)%4==0):
        count+=1
print(count)

但是在某些情况下，这样做会增加时间复杂度和内存限制。

这是我的提交结果：

有没有人能帮我减少时间复杂度和内存限制，提供更好的算法？

问题链接（这不是一个正在进行的比赛，仅供参考）

Answer 1

首先，虽然这不会改变你算法的复杂度顺序，但你可以通过6来缩小你检查的数字范围。因为你只需要检查那些等于 1 mod 12 或者等于 5 mod 12 的数字（比如 [1,5], [13,17], [25,29], [37,41] 等）。

由于你只需要计算那些是两个数字平方和的质数，顺序并不重要。因此，你可以把 range(a,b+1) 改成 range(1,b+1,12)+range(5,b+1,12)。

显然，你可以去掉函数 is_prime 中的 if n % 2 == 0 and n > 2 这个条件，另外，还可以把 if is_prime(i) and (i-1)%4 == 0 改成 if is_prime(i)。

最后，你可以通过只用那些靠近6的倍数的数字来检查每个数字是否是质数（比如 [5,7], [11,13], [17,19], [23,25] 等）。

所以你可以把这个：

range(3,int(math.sqrt(n))+1,2)

改成这个：

range(5,math.sqrt(n))+1,6)+range(7,math.sqrt(n))+1,6)

你也可以提前计算 math.sqrt(n))+1。

总结一下，这里是你可以提升程序整体性能的方法：

import math

def is_prime(n):
    max = int(math.sqrt(n))+1
    return all(n % i for i in range(5,max,6)+range(7,max,6))

count = 0
b = int(raw_input())
for i in range(1,b+1,12)+range(5,b+1,12):
    if is_prime(i):
        count += 1
print count

请注意，1 通常不被认为是质数，所以你可能想打印 count-1。另一方面，2 不等于 1 mod 4，但它是两个平方的和，所以你可以保持不变...

Answer 2

你可以通过把 for i in range(a,b+1): 改成 for i in xrange(a,b+1): 来减少内存的使用，这样就不会在内存中生成一个完整的列表。

你在下面的语句中也可以做同样的事情，不过你说得对，这样做对时间没有帮助。

return all(n % i for i in xrange(3, int(math.sqrt(n)) + 1, 2))

有一种一次性的优化方法，可能在内存消耗上不会像其他答案那样高，那就是使用 费马小定理。这个方法可以帮助你早早排除很多候选项。 更具体来说，你可以随机选择3到4个值来测试，如果其中一个被排除，那么你就可以直接排除这个候选项。否则，你可以继续进行你现在的测试。

Answer 3

不要一个个检查每个数字是不是质数。可以先计算出这个范围内所有的质数，使用一种叫做埃拉托斯特尼筛法的方法。这样做会大大简化你的工作。

因为你最多有2亿个数字，而且内存限制是256MB，每个数字至少需要4个字节，所以你需要想点小办法。不要把筛子初始化为所有小于y的数字，而是只用那些不能被2、3和5整除的数字。这样可以让筛子的初始大小小到可以放进内存里。

更新 正如Will Ness在评论中正确指出的，筛子里只存放标记，而不是数字，所以每个元素只需要1个字节，你甚至不需要这个预计算的小技巧。