Print the nodes with a prime degree in given Prufer sequence of a Tree | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void SieveOfEratosthenes ( bool 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 ; } } } void PrimeDegreeNodes ( int prufer [ ] , int n ) { int nodes = n + 2 ; bool prime [ nodes + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; SieveOfEratosthenes ( prime , nodes + 1 ) ; int degree [ 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 ] ] ) { cout << i << " ▁ " ; } } } int main ( ) { int a [ ] = { 4 , 1 , 3 , 4 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; PrimeDegreeNodes ( a , n ) ; return 0 ; }