//fermat's theorem: Every prime p>2 can be expressed as the sum 
//of the square of two integers x^2, y^2, that is  p=x^2+y^2 
//iff p==1 (mod 4). The integers p are called pythagorean primes
#include <iostream>
#include <cmath>
using namespace std;

bool PythogoreanPrime(int n);

int main()
{
    int p,x,y,isqrt;
    bool flag = false;

    do{
    cout << "Dose ena Pythagorean Prime > 2: ";
    cin >> p;
    } while (!PythogoreanPrime(p));
    isqrt=(int)sqrt(p);
    for(x = 1; x <= isqrt; ++x)
      for (y=x+1; y<=isqrt; y++)
        if (p==x*x+y*y)
           {
           cout << p << " = " << x*x << " + " << y*y << endl;
           flag = true; break;
            }

    if (!flag)
      cout << p << " den ekfrazetai san athroisma 2 tetragwnwn.";
    system("PAUSE"); 
    return 0;
}

// Elegxos gia pythagorean prime
bool PythogoreanPrime(int n)
{
    int i;
	bool isPrime = true, isPythPrime=false;
    for(i = 2; i <= n/2; ++i)
    {
        if(n % i == 0)
        {
            isPrime = false;
            break;
        }
    }
    if (isPrime && n%4==1) isPythPrime=true;
    return isPythPrime;
}