Check whether a number is Non | CPP program to check if a given number is Non - Hypotenuse number or not . ; Function to find prime factor and check if it is of the form 4 k + 1 or not ; 2 is a prime number but not of the form 4 k + 1 so , keep Dividing n by 2 until n is divisible by 2 ; n must be odd at this point . So we can skip one element ( Note i = i + 2 ) ; if i divides n check if i is of the form 4 k + 1 or not ; while i divides n divide n by i and update n ; This condition is to handle the case when n is a prime number greater than 2 ; Test function ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isNonHypotenuse ( int n ) { while ( n % 2 == 0 ) { n = n / 2 ; } for ( int i = 3 ; i <= sqrt ( n ) ; i = i + 2 ) { if ( n % i == 0 ) { if ( ( i - 1 ) % 4 == 0 ) return false ; while ( n % i == 0 ) { n = n / i ; } } } if ( n > 2 && ( n - 1 ) % 4 == 0 ) return false ; else return true ; } void test ( int n ) { cout << " Testing ▁ for ▁ " << n << " ▁ : ▁ " ; if ( isNonHypotenuse ( n ) ) cout << " YES " << " STRNEWLINE " ; else cout << " NO " << " STRNEWLINE " ; } int main ( ) { int n = 11 ; test ( n ) ; n = 10 ; test ( n ) ; return 0 ; }