# 使用Python 2.7.9的TWOSQRS SPOJ给出了运行时错误（NZEC）

``````    # -*- coding: utf-8 -*-
'''To solve the problem 2 primary condition that should be met are:
1. No should not be of the form 4k+3 as for sum of square of two nos will always be of form 4k or 4k+1
2. All the prime factors of form 4k+3 should have even power from the Fermat thorem.
Steps involved in solving the problem are:
1. Sieve a list of prime nos. upto 1000001 as in problem.
2. Check if all the prime factors has even powers.
3. Check if the no is not of form 4k+3'''

import numpy

def sieve(n):
""" An implementation that sieves separately
for primes of the form 6i−1 and 6i+1, due to Robert William Hanks"""

prime = numpy.ones(n//3 + (n%6==2), dtype=numpy.bool)
for i in range(3, int(n**.5) + 1, 3):
if prime[i // 3]:
p = (i + 1) | 1
prime[       p*p//3     ::2*p] = False
prime[p*(p-2*(i&1)+4)//3::2*p] = False
result = (3 * prime.nonzero()[0] + 1) | 1
result[0] = 3
return numpy.r_[2,result]

primes=sieve(10**6+1)            #List of all the prime upto 10**6

def main():
noOfCase=input()
for i in range(noOfCase):
N=input()
is_multiple= True
i = 0
while(primes[i]*primes[i] <= N):
count = 0;
while (N % primes[i] == 0):
count+=1;
N/= primes[i];
if (primes[i]%4 == 3 and count%2 == 1):
is_multiple = False;
break;
i+=1

if (N%4 == 3):
is_multiple = False
if(is_multiple):
print "Yes"
else:
print "No"

main()
``````

0条评论