Print the nodes with a prime degree in given Prufer sequence of a Tree | Java implementation to print the nodes with prime degree from the given prufer sequence ; 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
import java . util . * ; class GFG { static void SieveOfEratosthenes ( boolean prime [ ] , int p_size ) { prime [ 0 ] = false ; prime [ 1 ] = false ; for ( int p = 2 ; p * p <= p_size ; p ++ ) { if ( prime [ p ] ) { for ( int i = p * 2 ; i <= p_size ; i += p ) prime [ i ] = false ; } } } static void PrimeDegreeNodes ( int prufer [ ] , int n ) { int nodes = n + 2 ; boolean [ ] prime = new boolean [ nodes + 1 ] ; Arrays . fill ( prime , true ) ; SieveOfEratosthenes ( prime , nodes + 1 ) ; int [ ] degree = new int [ n + 2 + 1 ] ; for ( int i = 1 ; i <= nodes ; i ++ ) degree [ i ] = 1 ; for ( int i = 0 ; i < n ; i ++ ) degree [ prufer [ i ] ] ++ ; for ( int i = 1 ; i <= nodes ; i ++ ) { if ( prime [ degree [ i ] ] ) { System . out . print ( i + " ▁ " ) ; } } } public static void main ( String [ ] args ) { int a [ ] = { 4 , 1 , 3 , 4 } ; int n = a . length ; PrimeDegreeNodes ( a , n ) ; } }