Program to check whether a number is Proth number or not | CPP program to check Proth number ; Utility function to check power of two ; Function to check if the Given number is Proth number or not ; check if k divides n or not ; Check if n / k is power of 2 or not ; update k to next odd number ; If we reach here means there exists no value of K Such that k is odd number and n / k is a power of 2 greater than k ; Driver code ; Get n ; Check n for Proth Number
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPowerOfTwo ( int n ) { return ( n && ! ( n & ( n - 1 ) ) ) ; } bool isProthNumber ( int n ) { int k = 1 ; while ( k < ( n / k ) ) { if ( n % k == 0 ) { if ( isPowerOfTwo ( n / k ) ) return true ; } k = k + 2 ; } return false ; } int main ( ) { int n = 25 ; if ( isProthNumber ( n - 1 ) ) cout << " YES " ; else cout << " NO " ; return 0 ; }