Check if a number is Fermat Pseudoprime | 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
function checkcomposite ( n ) { for ( let i = 2 ; i <= Math . sqrt ( n ) ; i ++ ) { if ( n % i == 0 ) return 1 ; } return 0 ; } function power ( x , y , mod ) { let res = 1 ; while ( y ) { if ( y & 1 ) res = ( res * x ) % mod ; y = y >> 1 ; x = ( x * x ) % mod ; } return res ; } function Check ( n , a ) { if ( a > 1 && checkcomposite ( n ) && power ( a , n - 1 , n ) == 1 ) return 1 ; return 0 ; } let N = 645 ; let a = 2 ; document . write ( Check ( N , a ) ) ;