PYTHAEQ - Phương trình Pythagore nghiệm nguyên

Tác giả: khuc_tuan

Ngôn ngữ: Python

isPrime = [True for x in range(45000)]
isPrime[0] = isPrime[1] = False
for i in range(2,45000):
    if isPrime[i]:
        for j in range(i+i,45000,i): isPrime[j]=False
n = input()
res = 4
for i in range(2,45000):
    if isPrime[i]:
        t=0
        while n%i==0:
            n/=i
            t=t+1
        if i%4==1 and t!=0: res *= t*2+1
    if i*i>n: break
if n!=1 and n%4==1: res *=3
print res

Download