Algorithm
Problem link- https://www.spoj.com/problems/TWOSQRS/
TWOSQRS - Two squares or not two squares
Given integer n decide if it is possible to represent it as a sum of two squares of integers.
Input
First line of input contains one integer c <= 100 - number of test cases. Then c lines follow, each of them consisting of exactly one integer 0 <= n <= 10^12.
Output
For each test case output Yes if it is possible to represent given number as a sum of two squares and No if it is not possible.
Example
Input: 10 1 2 7 14 49 9 17 76 2888 27 Output: Yes Yes No No Yes Yes Yes No Yes No
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
using namespace std;
int main(){
int t=0;
long long n;
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
bool good = true;
for (long long i=2; i*i<n; i++){
int ct=0;
while(n%i==0){
ct++;
n/=i;
}
if(i%4==3&&ct%2==1){
good=false;
break;
}
}
if(n%4==3)good=false;
if(good) printf("Yes\n");
else printf("No\n");
}
}Input
10
1
2
7
14
49
9
17
76
2888
27
1
2
7
14
49
9
17
76
2888
27
Output
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
No
Yes
No
No
Yes
Yes
Yes
No
Yes
No
Demonstration
SPOJ Solution-Two squares or not two squares-Solution in C, C++, Java, Python