Check if a number is Fermat Pseudoprime | C ++ program to check if N is Fermat pseudoprime to the base A or not ; Function to check if the given number is composite ; Check if there is any divisor of n less than sqrt ( n ) ; Effectively calculate ( x ^ y ) modulo mod ; Initialize result ; If power is odd , then update the answer ; Square the number and reduce the power to its half ; Return the result ; Function to check for Fermat Pseudoprime ; If it is composite and satisfy Fermat criterion ; Else return 0 ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool checkcomposite ( int n ) { for ( int i = 2 ; i <= sqrt ( n ) ; i ++ ) { if ( n % i == 0 ) return 1 ; } return 0 ; } int power ( int x , int y , int mod ) { int res = 1 ; while ( y ) { if ( y & 1 ) res = ( res * x ) % mod ; y = y >> 1 ; x = ( x * x ) % mod ; } return res ; } bool Check ( int n , int a ) { if ( a > 1 && checkcomposite ( n ) && power ( a , n - 1 , n ) == 1 ) return 1 ; return 0 ; } int main ( ) { int N = 645 ; int a = 2 ; cout << Check ( N , a ) ; return 0 ; }