Count of all prime weight nodes between given nodes in the given Tree | Javascript program Count prime weight nodes between two nodes in the given tree ; Function to perform Sieve Of Eratosthenes for prime number ; Initialize all entries of prime it as true a value in prime [ i ] will finally be false if i is Not a prime , else true . ; Check if prime [ p ] is not changed , then it is a prime ; Update all multiples of p greater than or equal to the square of it numbers which are multiple of p and are less than p ^ 2 are already been marked . ; Function to perform dfs ; Stores parent of each node ; Stores level of each node from root ; Function to perform prime number between the path ; The node which is present farthest from the root node is taken as v If u is farther from root node then swap the two ; Find the ancestor of v which is at same level as u ; If Weight is prime increment count ; If u is the ancestor of v then u is the LCA of u and v Now check if weigh [ v ] is prime or not ; When v and u are on the same level but are in different subtree . Now move both u and v up by 1 till they are not same ; If weight of first ancestor is prime ; Precompute all the prime numbers till MAX ; Weights of the node ; Edges of the tree
var MAX = 1000 ; var weight = Array ( MAX ) ; var level = Array ( MAX ) ; var par = Array ( MAX ) ; var prime = Array ( MAX + 1 ) . fill ( true ) ; var graph = Array . from ( Array ( MAX ) , ( ) => Array ( ) ) ; function SieveOfEratosthenes ( ) { for ( var p = 2 ; p * p <= MAX ; p ++ ) { if ( prime [ p ] == true ) { for ( var i = p * p ; i <= MAX ; i += p ) prime [ i ] = false ; } } } function dfs ( node , parent , h ) { par [ node ] = parent ; level [ node ] = h ; graph [ node ] . forEach ( child => { if ( child != parent ) dfs ( child , node , h + 1 ) ; } ) ; } function findPrimeOnPath ( u , v ) { var count = 0 ; if ( level [ u ] > level [ v ] ) { [ u , v ] = [ v , u ] } var d = level [ v ] - level [ u ] ; while ( d -- ) { if ( prime [ weight [ v ] ] ) count ++ ; v = par [ v ] ; } if ( v == u ) { if ( prime [ weight [ v ] ] ) count ++ ; return count ; } while ( v != u ) { if ( prime [ weight [ v ] ] ) count ++ ; if ( prime [ weight [ u ] ] ) count ++ ; u = par [ u ] ; v = par [ v ] ; } if ( prime [ weight [ v ] ] ) count ++ ; return count ; } SieveOfEratosthenes ( ) ; weight [ 1 ] = 5 ; weight [ 2 ] = 10 ; weight [ 3 ] = 11 ; weight [ 4 ] = 8 ; weight [ 5 ] = 6 ; graph [ 1 ] . push ( 2 ) ; graph [ 2 ] . push ( 3 ) ; graph [ 2 ] . push ( 4 ) ; graph [ 1 ] . push ( 5 ) ; dfs ( 1 , - 1 , 0 ) ; var u = 3 , v = 5 ; document . write ( findPrimeOnPath ( u , v ) ) ;