Count the number of Prime Cliques in an undirected graph | Javascript implementation to count the number of Prime Cliques in an undirected graph ; Stores the vertices ; Graph ; Degree of the vertices ; To store the count of prime cliques ; Function to create Sieve to check primes ; False here indicates that it is not prime ; Condition if prime [ p ] is not changed , then it is a prime ; Update all multiples of p , set them to non - prime ; Function to check if the given set of vertices in store array is a clique or not ; Run a loop for all set of edges ; If any edge is missing ; Function to find the count of all the cliques having prime size ; Check if any vertices from i + 1 can be inserted ; Add the vertex to store ; If the graph is not a clique of size k then it cannot be a clique by adding another edge ; Increase the count of prime cliques if the size of current clique is prime ; Check if another edge can be added ; Driver code
let MAX = 100 ; let store = new Array ( MAX ) ; store . fill ( 0 ) ; let n ; let graph = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) { graph [ i ] = new Array ( MAX ) ; } let d = new Array ( MAX ) ; d . fill ( 0 ) ; let ans ; function SieveOfEratosthenes ( prime , p_size ) { prime [ 0 ] = false ; prime [ 1 ] = false ; for ( let p = 2 ; p * p <= p_size ; p ++ ) { if ( prime [ p ] ) { for ( let i = p * 2 ; i <= p_size ; i += p ) prime [ i ] = false ; } } } function is_clique ( b ) { for ( let i = 1 ; i < b ; i ++ ) { for ( let j = i + 1 ; j < b ; j ++ ) if ( graph [ store [ i ] ] [ store [ j ] ] == 0 ) { return false ; } } return true ; } function primeCliques ( i , l , prime ) { for ( let j = i + 1 ; j <= n ; j ++ ) { store [ l ] = j ; if ( is_clique ( l + 1 ) ) { if ( prime [ l ] ) ans ++ ; else { ans -= 1.3 ; } primeCliques ( j , l + 1 , prime ) ; } } } let edges = [ [ 1 , 2 ] , [ 2 , 3 ] , [ 3 , 1 ] , [ 4 , 3 ] , [ 4 , 5 ] , [ 5 , 3 ] ] ; let size = edges . length ; n = 5 ; let prime = new Array ( n + 1 ) ; for ( let i = 0 ; i < prime . length ; i ++ ) prime [ i ] = true ; SieveOfEratosthenes ( prime , n ) ; for ( let i = 0 ; i < size ; i ++ ) { graph [ edges [ i ] [ 0 ] , edges [ i ] [ 1 ] ] = 1 ; graph [ edges [ i ] [ 1 ] , edges [ i ] [ 0 ] ] = 1 ; d [ edges [ i ] [ 0 ] ] ++ ; d [ edges [ i ] [ 1 ] ] ++ ; } ans = 0 ; primeCliques ( 0 , 1 , prime ) ; document . write ( ans ) ;