Print the nodes with a prime degree in given Prufer sequence of a Tree | Function to create Sieve to check primes ; False here indicates that it is not prime ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p , set them to non - prime ; Function to print the nodes with prime degree in the tree whose Prufer sequence is given ; Hash - table to mark the degree of every node ; Initially let all the degrees be 1 ; Increase the count of the degree ; Print the nodes with prime degree ; Driver Code
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 PrimeDegreeNodes ( prufer , n ) { let nodes = n + 2 ; let prime = new Array ( nodes + 1 ) ; prime . fill ( true ) ; SieveOfEratosthenes ( prime , nodes + 1 ) ; let degree = new Array ( n + 2 + 1 ) ; for ( let i = 1 ; i <= nodes ; i ++ ) degree [ i ] = 1 ; for ( let i = 0 ; i < n ; i ++ ) degree [ prufer [ i ] ] ++ ; for ( let i = 1 ; i <= nodes ; i ++ ) { if ( prime [ degree [ i ] ] ) { document . write ( i + " " ) ; } } } let a = [ 4 , 1 , 3 , 4 ] ; let n = a . length PrimeDegreeNodes ( a , n ) ;