Given an undirected graph with N vertices and M edges, the task is to print all the nodes of the given graph whose degree is a Prime Number.
Examples:
Input: N = 4, arr[][] = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 } }
Output: 1 2 3 4
Explanation:
Below is the graph for the above information:
The degree of the node as per above graph is:
Node -> Degree
1 -> 3
2 -> 3
3 -> 3
4 -> 3
Hence, the nodes with prime degree are 1 2 3 4
Input: N = 5, arr[][] = { { 1, 2 }, { 1, 3 }, { 2, 4 }, { 2, 5 } }
Output: 1
Approach:
- Use Sieve of Eratosthenes to calculate the prime numbers up to 105.
- For each vertex, the degree can be calculated by the length of the Adjacency List of the given graph at the corresponding vertex.
- Print those vertices of the given graph whose degree is a Prime Number.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;int n = 10005;// To store Prime Numbersvector<bool> Prime(n + 1, true);// Function to find the prime numbers// till 10^5void SieveOfEratosthenes(){ int i, j; Prime[0] = Prime[1] = false; for (i = 2; i * i <= 10005; i++) { // Traverse all multiple of i // and make it false if (Prime[i]) { for (j = 2 * i; j < 10005; j += i) { Prime[j] = false; } } }}// Function to print the nodes having// prime degreevoid primeDegreeNodes(int N, int M, int edges[][2]){ // To store Adjacency List of // a Graph vector<int> Adj[N + 1]; // Make Adjacency List for (int i = 0; i < M; i++) { int x = edges[i][0]; int y = edges[i][1]; Adj[x].push_back(y); Adj[y].push_back(x); } // To precompute prime numbers // till 10^5 SieveOfEratosthenes(); // Traverse each vertex for (int i = 1; i <= N; i++) { // Find size of Adjacency List int x = Adj[i].size(); // If length of Adj[i] is Prime // then print it if (Prime[x]) cout << i << ' '; }}// Driver codeint main(){ // Vertices and Edges int N = 4, M = 6; // Edges int edges[M][2] = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 } }; // Function Call primeDegreeNodes(N, M, edges); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{static int n = 10005;// To store Prime Numbersstatic boolean []Prime = new boolean[n + 1];// Function to find the prime numbers// till 10^5static void SieveOfEratosthenes(){ int i, j; Prime[0] = Prime[1] = false; for (i = 2; i * i <= 10005; i++) { // Traverse all multiple of i // and make it false if (Prime[i]) { for (j = 2 * i; j < 10005; j += i) { Prime[j] = false; } } }}// Function to print the nodes having// prime degreestatic void primeDegreeNodes(int N, int M, int edges[][]){ // To store Adjacency List of // a Graph Vector<Integer> []Adj = new Vector[N + 1]; for(int i = 0; i < Adj.length; i++) Adj[i] = new Vector<Integer>(); // Make Adjacency List 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); } // To precompute prime numbers // till 10^5 SieveOfEratosthenes(); // Traverse each vertex for (int i = 1; i <= N; i++) { // Find size of Adjacency List int x = Adj[i].size(); // If length of Adj[i] is Prime // then print it if (Prime[x]) System.out.print(i + " "); }}// Driver codepublic static void main(String[] args){ // Vertices and Edges int N = 4, M = 6; // Edges int edges[][] = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 } }; Arrays.fill(Prime, true); // Function Call primeDegreeNodes(N, M, edges);}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 implementation of # the above approachn = 10005; # To store Prime NumbersPrime = [True for i in range(n + 1)] # Function to find # the prime numbers # till 10^5def SieveOfEratosthenes(): i = 2 Prime[0] = Prime[1] = False; while i * i <= 10005: # Traverse all multiple # of i and make it false if (Prime[i]): for j in range(2 * i, 10005): Prime[j] = False i += 1 # Function to print the # nodes having prime degreedef primeDegreeNodes(N, M, edges): # To store Adjacency # List of a Graph Adj = [[] for i in range(N + 1)]; # Make Adjacency List for i in range(M): x = edges[i][0]; y = edges[i][1]; Adj[x].append(y); Adj[y].append(x); # To precompute prime # numbers till 10^5 SieveOfEratosthenes(); # Traverse each vertex for i in range(N + 1): # Find size of Adjacency List x = len(Adj[i]); # If length of Adj[i] is Prime # then print it if (Prime[x]): print(i, end = ' ') # Driver codeif __name__ == "__main__": # Vertices and Edges N = 4 M = 6 # Edges edges = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]; # Function Call primeDegreeNodes(N, M, edges);# This code is contributed by rutvik_56 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{static int n = 10005;// To store Prime Numbersstatic bool []Prime = new bool[n + 1];// Function to find the prime numbers// till 10^5static void SieveOfEratosthenes(){ int i, j; Prime[0] = Prime[1] = false; for(i = 2; i * i <= 10005; i++) { // Traverse all multiple of i // and make it false if (Prime[i]) { for(j = 2 * i; j < 10005; j += i) { Prime[j] = false; } } }}// Function to print the nodes having// prime degreestatic void primeDegreeNodes(int N, int M, int [,]edges){ // To store Adjacency List of // a Graph List<int> []Adj = new List<int>[N + 1]; for(int i = 0; i < Adj.Length; i++) Adj[i] = new List<int>(); // Make Adjacency List 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); } // To precompute prime numbers // till 10^5 SieveOfEratosthenes(); // Traverse each vertex for(int i = 1; i <= N; i++) { // Find size of Adjacency List int x = Adj[i].Count; // If length of Adj[i] is Prime // then print it if (Prime[x]) Console.Write(i + " "); }}// Driver codepublic static void Main(String[] args){ // Vertices and Edges int N = 4, M = 6; // Edges int [,]edges = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 } }; for(int i = 0; i < Prime.Length; i++) Prime[i] = true; // Function Call primeDegreeNodes(N, M, edges);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approachlet n = 10005;// To store Prime Numberslet Prime = new Array(n + 1).fill(true);// Function to find the prime numbers// till 10^5function SieveOfEratosthenes(){ let i, j; Prime[0] = Prime[1] = false; for (i = 2; i * i <= 10005; i++) { // Traverse all multiple of i // and make it false if (Prime[i]) { for (j = 2 * i; j < 10005; j += i) { Prime[j] = false; } } }}// Function to print the nodes having// prime degreefunction primeDegreeNodes(N, M, edges){ // To store Adjacency List of // a Graph let Adj = new Array(); for(let i = 0; i < N + 1; i++){ Adj.push(new Array()) } // Make Adjacency List for (let i = 0; i < M; i++) { let x = edges[i][0]; let y = edges[i][1]; Adj[x].push(y); Adj[y].push(x); } // To precompute prime numbers // till 10^5 SieveOfEratosthenes(); // Traverse each vertex for (let i = 1; i <= N; i++) { // Find size of Adjacency List let x = Adj[i].length; // If length of Adj[i] is Prime // then print it if (Prime[x]) document.write(i + ' '); }}// Driver code// Vertices and Edgeslet N = 4, M = 6; // Edgeslet edges = [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ];// Function CallprimeDegreeNodes(N, M, edges);// This code is contributed by gfgking</script> |
1 2 3 4
Time Complexity: O(N + M), where N is the number of vertices and M is the number of edges.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!


… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/nodes-with-prime-degree-in-an-undirected-graph/ […]
… [Trackback]
[…] There you will find 73834 more Information on that Topic: geeksforgeeks.org/nodes-with-prime-degree-in-an-undirected-graph/ […]
… [Trackback]
[…] Find More Info here on that Topic: geeksforgeeks.org/nodes-with-prime-degree-in-an-undirected-graph/ […]
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/nodes-with-prime-degree-in-an-undirected-graph/ […]
… [Trackback]
[…] Here you can find 30301 more Information to that Topic: geeksforgeeks.org/nodes-with-prime-degree-in-an-undirected-graph/ […]