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
def SieveOfEratosthenes ( prime , p_size ) : NEW_LINE INDENT prime [ 0 ] = False NEW_LINE prime [ 1 ] = False NEW_LINE p = 2 NEW_LINE while ( p * p <= p_size ) : NEW_LINE INDENT if ( prime [ p ] ) : NEW_LINE INDENT for i in range ( p * 2 , p_size + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT DEDENT def PrimeDegreeNodes ( prufer , n ) : NEW_LINE INDENT nodes = n + 2 NEW_LINE prime = [ True ] * ( nodes + 1 ) NEW_LINE SieveOfEratosthenes ( prime , nodes + 1 ) NEW_LINE degree = [ 0 ] * ( n + 2 + 1 ) ; NEW_LINE for i in range ( 1 , nodes + 1 ) : NEW_LINE INDENT degree [ i ] = 1 ; NEW_LINE DEDENT for i in range ( 0 , n ) : NEW_LINE INDENT degree [ prufer [ i ] ] += 1 NEW_LINE DEDENT for i in range ( 1 , nodes + 1 ) : NEW_LINE INDENT if prime [ degree [ i ] ] : NEW_LINE INDENT print ( i , end = ' ▁ ' ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ 4 , 1 , 3 , 4 ] NEW_LINE n = len ( a ) NEW_LINE PrimeDegreeNodes ( a , n ) NEW_LINE DEDENT