素数可以写成两个数字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)

但在某些情况下,这会增加时间复杂度和内存限制.

这是我提交的结果:

任何人都可以用更好的算法帮助我减少时间复杂度和内存限制吗？

问题链接(不是正在进行的比赛FYI)

Answer 1

不要检查每个数字是否为素数.使用Sieve of Eratosthenes预先计算该范围内的所有素数.这将大大降低复杂性.

由于您拥有最多200M的数字和256Mb的内存限制,并且每个数字至少需要4个字节,因此您需要一点点破解.不要使用所有数字来初始化筛子y,但只能使用不能被2,3和5整除的数字.这将使筛子的初始尺寸减小到足以满足内存限制.

UPD正如Will Ness在评论中正确指出的那样,筛选仅包含标志,而不包含数字,因此每个元素需要不超过1个字节,您甚至不需要这个预先计算的hack.