AKS Primality Test | C ++ code to check if number is prime . This program demonstrates concept behind AKS algorithm and doesn 't implement the actual algorithm (This works only till n = 64) ; 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 program
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long c [ 100 ] ; void coef ( int n ) { c [ 0 ] = 1 ; for ( int i = 0 ; i < n ; c [ 0 ] = - c [ 0 ] , i ++ ) { c [ 1 + i ] = 1 ; for ( int j = i ; j > 0 ; j -- ) c [ j ] = c [ j - 1 ] - c [ j ] ; } } bool isPrime ( int n ) { coef ( n ) ; c [ 0 ] ++ , c [ n ] -- ; int i = n ; while ( i -- && c [ i ] % n == 0 ) ; return i < 0 ; } int main ( ) { int n = 37 ; if ( isPrime ( n ) ) cout << " Prime " << endl ; else cout << " Not ▁ Prime " << endl ; return 0 ; }