Nodes with prime degree in an undirected Graph | Java implementation of the approach ; To store Prime Numbers ; Function to find the prime numbers till 10 ^ 5 ; Traverse all multiple of i and make it false ; Function to print the nodes having prime degree ; To store Adjacency List of a Graph ; Make Adjacency List ; To precompute prime numbers till 10 ^ 5 ; Traverse each vertex ; Find size of Adjacency List ; If length of Adj [ i ] is Prime then print it ; Driver code ; Vertices and Edges ; Edges ; Function Call
import java . util . * ; class GFG { static int n = 10005 ; static boolean [ ] Prime = new boolean [ n + 1 ] ; static void SieveOfEratosthenes ( ) { int i , j ; Prime [ 0 ] = Prime [ 1 ] = false ; for ( i = 2 ; i * i <= 10005 ; i ++ ) { if ( Prime [ i ] ) { for ( j = 2 * i ; j < 10005 ; j += i ) { Prime [ j ] = false ; } } } } static void primeDegreeNodes ( int N , int M , int edges [ ] [ ] ) { Vector < Integer > [ ] Adj = new Vector [ N + 1 ] ; for ( int i = 0 ; i < Adj . length ; i ++ ) Adj [ i ] = new Vector < Integer > ( ) ; for ( int i = 0 ; i < M ; i ++ ) { int x = edges [ i ] [ 0 ] ; int y = edges [ i ] [ 1 ] ; Adj [ x ] . add ( y ) ; Adj [ y ] . add ( x ) ; } SieveOfEratosthenes ( ) ; for ( int i = 1 ; i <= N ; i ++ ) { int x = Adj [ i ] . size ( ) ; if ( Prime [ x ] ) System . out . print ( i + " ▁ " ) ; } } public static void main ( String [ ] args ) { int N = 4 , M = 6 ; int edges [ ] [ ] = { { 1 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 3 } , { 2 , 4 } , { 3 , 4 } } ; Arrays . fill ( Prime , true ) ; primeDegreeNodes ( N , M , edges ) ; } }