AKS Primality Test | array used to store coefficients . ; function to calculate the coefficients of ( x - 1 ) ^ n - ( x ^ n - 1 ) with the help of Pascal 's triangle . ; function to check whether the number is prime or not ; Calculating all the coefficients by the function coef and storing all the coefficients in c array . ; subtracting c [ n ] and adding c [ 0 ] by 1 as ( x - 1 ) ^ n - ( x ^ n - 1 ) , here we are subtracting c [ n ] by 1 and adding 1 in expression . ; checking all the coefficients whether they are divisible by n or not . if n is not prime , then loop breaks and ( i > 0 ) . ; Return true if all coefficients are divisible by n . ; Driver Code
c = [ 0 ] * 100 ; NEW_LINE def coef ( n ) : NEW_LINE INDENT c [ 0 ] = 1 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT c [ 1 + i ] = 1 ; NEW_LINE for j in range ( i , 0 , - 1 ) : NEW_LINE INDENT c [ j ] = c [ j - 1 ] - c [ j ] ; NEW_LINE DEDENT c [ 0 ] = - c [ 0 ] ; NEW_LINE DEDENT DEDENT def isPrime ( n ) : NEW_LINE INDENT coef ( n ) ; NEW_LINE c [ 0 ] = c [ 0 ] + 1 ; NEW_LINE c [ n ] = c [ n ] - 1 ; NEW_LINE i = n ; NEW_LINE while ( i > - 1 and c [ i ] % n == 0 ) : NEW_LINE INDENT i = i - 1 ; NEW_LINE DEDENT return True if i < 0 else False ; NEW_LINE DEDENT n = 37 ; NEW_LINE if ( isPrime ( n ) ) : NEW_LINE INDENT print ( " Prime " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not ▁ Prime " ) ; NEW_LINE DEDENT