Nodes with prime degree in an undirected Graph | JavaScript implementation of the approach ; To store Prime Numbers ; Function to find the prime numbers till 10 ^ 5 ; Traverse all multiple of i and make it false ; Function to print the nodes having prime degree ; To store Adjacency List of a Graph ; Make Adjacency List ; To precompute prime numbers till 10 ^ 5 ; Traverse each vertex ; Find size of Adjacency List ; If length of Adj [ i ] is Prime then print it ; Vertices and Edges ; Edges ; Function Call
let n = 10005 ; let Prime = new Array ( n + 1 ) . fill ( true ) ; function SieveOfEratosthenes ( ) { let i , j ; Prime [ 0 ] = Prime [ 1 ] = false ; for ( i = 2 ; i * i <= 10005 ; i ++ ) { if ( Prime [ i ] ) { for ( j = 2 * i ; j < 10005 ; j += i ) { Prime [ j ] = false ; } } } } function primeDegreeNodes ( N , M , edges ) { let Adj = new Array ( ) ; for ( let i = 0 ; i < N + 1 ; i ++ ) { Adj . push ( new Array ( ) ) } for ( let i = 0 ; i < M ; i ++ ) { let x = edges [ i ] [ 0 ] ; let y = edges [ i ] [ 1 ] ; Adj [ x ] . push ( y ) ; Adj [ y ] . push ( x ) ; } SieveOfEratosthenes ( ) ; for ( let i = 1 ; i <= N ; i ++ ) { let x = Adj [ i ] . length ; if ( Prime [ x ] ) document . write ( i + ' ' ) ; } } let N = 4 , M = 6 ; let edges = [ [ 1 , 2 ] , [ 1 , 3 ] , [ 1 , 4 ] , [ 2 , 3 ] , [ 2 , 4 ] , [ 3 , 4 ] ] ; primeDegreeNodes ( N , M , edges ) ;