Check if a number is Fermat Pseudoprime | Java 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
class GFG { static boolean checkcomposite ( int n ) { for ( int i = 2 ; i <= Math . sqrt ( n ) ; i ++ ) { if ( n % i == 0 ) { return true ; } } return false ; } static int power ( int x , int y , int mod ) { int res = 1 ; while ( y != 0 ) { if ( ( y & 1 ) == 1 ) { res = ( res * x ) % mod ; } y = y >> 1 ; x = ( x * x ) % mod ; } return res ; } static int Check ( int n , int a ) { if ( a > 1 && checkcomposite ( n ) && power ( a , n - 1 , n ) == 1 ) { return 1 ; } return 0 ; } public static void main ( String [ ] args ) { int N = 645 ; int a = 2 ; System . out . println ( Check ( N , a ) ) ; } }