#include <iostream>

// This program queries the user for an integer 'n'
// and determines whether it can be written as the
// sum of the squares of two positive integers:
//
//     n = m1*m1 + m2*m2,
//
// where
//
//     1 <= m1 <= m2.
//
// If such a representation is found, print it.
// Otherwise, report that no such representation
// exists.
//
// Exercises:
//
// 1. Rewrite the first part of the program so that
//    the user is repeatedly queried until an integer
//    greater than or equal to 1 is entered.
//
// 2. The outer for loop currently continues as long
//    as
//
//        m1 < n.
//
//    Suppose instead that
//
//        m1*m1 >= n.
//
//    Since m2 >= m1 and m2 must be positive, can
//    m1*m1 + m2*m2 possibly equal n?
//
//    Modify the condition of the outer loop so that
//    the loop terminates as soon as there is no
//    longer any possibility of finding a solution.
//
// 3. The inner for loop currently continues as long
//    as
//
//        m2 < n.
//
//    However, for a fixed value of m1, the quantity
//
//        m1*m1 + m2*m2
//
//    increases as m2 increases.
//
//    If
//
//        m1*m1 + m2*m2 > n,
//
//    is there any reason to try still larger values
//    of m2?
//
//    Modify the inner loop so that it terminates as
//    soon as the sum becomes greater than n.

// Function declarations
int main();

// Function definitions
int main() {
    int n{};

    std::cout << "Enter an integer: ";
    std::cin  >> n;

    bool is_found{ false };

    int m1{};
    int m2{};

    for ( m1 = 1; m1 < n; ++m1 ) {
        for ( m2 = m1; m2 < n; ++m2 ) {
            if ( m1*m1 + m2*m2 == n ) {
                is_found = true;
                break;
            }
        }

        if ( is_found ) {
            break;
        }
    }

    if ( is_found ) {
        std::cout << n << " = "
                  << m1 << "^2 + "
                  << m2 << "^2"
                  << std::endl;
    } else {
        std::cout << n
                  << " is not the sum of two "
                  << "non-zero squares."
                  << std::endl;
    }

    return 0;
}



























// Hint for Exercise 1:
//
// You have already seen how
//
//     while ( true ) {
//
// together with a 'break' statement can repeatedly
// query the user until an acceptable value is entered.



























// Hint for Exercise 2:
//
// The outer loop does not need to continue once
//
//     m1*m1 >= n.
//
// Therefore, can this condition be incorporated
// directly into the condition of the for loop?



























// Hint for Exercise 3:
//
// Once
//
//     m1*m1 + m2*m2 > n,
//
// increasing m2 will only make the sum larger.
//
// You could test for this inside the loop and use
// 'break', but can you instead incorporate the
// condition directly into the condition of the
// inner for loop?



























// Here is one solution:
/*
int main() {
    int n{};

    while ( true ) {
        std::cout << "Enter an integer greater than "
                  << "or equal to 1: ";
        std::cin  >> n;

        if ( n >= 1 ) {
            break;
        }
    }

    bool is_found{ false };

    int m1{};
    int m2{};

    for ( m1 = 1; m1*m1 < n; ++m1 ) {
        for ( m2 = m1;
              m1*m1 + m2*m2 <= n;
              ++m2 ) {
            if ( m1*m1 + m2*m2 == n ) {
                is_found = true;
                break;
            }
        }

        if ( is_found ) {
            break;
        }
    }

    if ( is_found ) {
        std::cout << n << " = "
                  << m1 << "^2 + "
                  << m2 << "^2"
                  << std::endl;
    } else {
        std::cout << n
                  << " is not the sum of two "
                  << "non-zero squares."
                  << std::endl;
    }

    return 0;
}
*/