Given a singly linked list containing N nodes, the task is to find the total count of prime numbers.
Input: List = 15 -> 5 -> 6 -> 10 -> 17
Output: 2
5 and 17 are the prime nodes
Input: List = 29 -> 3 -> 4 -> 2 -> 9
Output: 3
2, 3 and 29 are the prime nodes
Approach: The idea is to traverse the linked list to the end and check if the current node is prime or not. If YES, increment the count by 1 and keep doing the same until all the nodes get traversed.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
bool isPrime( int n)
{
if (n <= 1)
return false ;
if (n <= 3)
return true ;
if (n % 2 == 0 || n % 3 == 0)
return false ;
for ( int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false ;
return true ;
}
int countPrime(Node** head_ref)
{
int count = 0;
Node* ptr = *head_ref;
while (ptr != NULL) {
if (isPrime(ptr->data)) {
count++;
}
ptr = ptr->next;
}
return count;
}
int main()
{
Node* head = NULL;
push(&head, 17);
push(&head, 10);
push(&head, 6);
push(&head, 5);
push(&head, 15);
cout << "Count of prime nodes = "
<< countPrime(&head);
return 0;
}
|
Java
class solution
{
static class Node {
int data;
Node next;
}
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = ( head_ref);
( head_ref) = new_node;
return head_ref;
}
static boolean isPrime( int n)
{
if (n <= 1 )
return false ;
if (n <= 3 )
return true ;
if (n % 2 == 0 || n % 3 == 0 )
return false ;
for ( int i = 5 ; i * i <= n; i = i + 6 )
if (n % i == 0 || n % (i + 2 ) == 0 )
return false ;
return true ;
}
static int countPrime(Node head_ref)
{
int count = 0 ;
Node ptr = head_ref;
while (ptr != null ) {
if (isPrime(ptr.data)) {
count++;
}
ptr = ptr.next;
}
return count;
}
public static void main(String args[])
{
Node head = null ;
head=push(head, 17 );
head=push(head, 10 );
head=push(head, 6 );
head=push(head, 5 );
head=push(head, 15 );
System.out.print( "Count of prime nodes = " + countPrime(head));
}
}
|
Python3
def isPrime(n):
if n < = 1 :
return False
if n < = 3 :
return True
if n % 2 = = 0 or n % 3 = = 0 :
return False
i = 5
while i * i < = n:
if n % i = = 0 or n % (i + 2 ) = = 0 :
return False
i + = 6
return True
class Node:
def __init__( self , data, next ):
self .data = data
self . next = next
class LinkedList:
def __init__( self ):
self .head = None
def push( self , new_data):
new_node = Node(new_data, self .head)
self .head = new_node
def countPrime( self ):
count = 0
ptr = self .head
while ptr ! = None :
if isPrime(ptr.data):
count + = 1
ptr = ptr. next
return count
if __name__ = = "__main__" :
linkedlist = LinkedList()
linkedlist.push( 17 )
linkedlist.push( 10 )
linkedlist.push( 6 )
linkedlist.push( 5 )
linkedlist.push( 15 )
print ( "Count of prime nodes =" ,
linkedlist.countPrime())
|
C#
using System;
class GFG
{
public class Node
{
public int data;
public Node next;
}
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = ( head_ref);
( head_ref) = new_node;
return head_ref;
}
static bool isPrime( int n)
{
if (n <= 1)
return false ;
if (n <= 3)
return true ;
if (n % 2 == 0 || n % 3 == 0)
return false ;
for ( int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false ;
return true ;
}
static int countPrime(Node head_ref)
{
int count = 0;
Node ptr = head_ref;
while (ptr != null )
{
if (isPrime(ptr.data))
{
count++;
}
ptr = ptr.next;
}
return count;
}
public static void Main(String []args)
{
Node head = null ;
head=push(head, 17);
head=push(head, 10);
head=push(head, 6);
head=push(head, 5);
head=push(head, 15);
Console.Write( "Count of prime nodes = " + countPrime(head));
}
}
|
Javascript
<script>
class Node
{
constructor(val)
{
this .data = val;
this .next = null ;
}
}
function push(head_ref, new_data)
{
var new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
function isPrime(n)
{
if (n <= 1)
return false ;
if (n <= 3)
return true ;
if (n % 2 == 0 || n % 3 == 0)
return false ;
for (i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false ;
return true ;
}
function countPrime(head_ref)
{
var count = 0;
var ptr = head_ref;
while (ptr != null )
{
if (isPrime(ptr.data))
{
count++;
}
ptr = ptr.next;
}
return count;
}
var head = null ;
head = push(head, 17);
head = push(head, 10);
head = push(head, 6);
head = push(head, 5);
head = push(head, 15);
document.write( "Count of prime nodes = " +
countPrime(head));
</script>
|
Output
Count of prime nodes = 2
- Time Complexity: O(N*sqrt(P)), where N is length of the LinkedList and P is the maximum element in the List
- Auxiliary Space: O(1)
The base case of the recursion is when the head node is NULL, in which case the function returns 0. Otherwise, the function first calls itself recursively for the next node in the linked list, and obtains the count of prime nodes in the remaining linked list. If the data of the current node is prime, it adds 1 to the count and returns it, otherwise it simply returns the count obtained from the recursive call. The final result returned by the function is the count of prime nodes in the entire linked list.
- If the head node is NULL, return 0.
- Recursively call the function for the rest of the linked list by passing the next node.
- If the data of the current node is prime, add 1 to the count and return it.
- Otherwise, return the count obtained from the recursive call.
Below is the implementation of the above approach:
C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
void push(Node** head_ref, int new_data) {
Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
bool isPrime( int n) {
if (n <= 1)
return false ;
if (n <= 3)
return true ;
if (n % 2 == 0 || n % 3 == 0)
return false ;
for ( int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false ;
return true ;
}
int countPrimeRecursive(Node* head) {
if (head == NULL)
return 0;
int count = countPrimeRecursive(head->next);
if (isPrime(head->data))
count++;
return count;
}
int main() {
Node* head = NULL;
push(&head, 17);
push(&head, 10);
push(&head, 6);
push(&head, 5);
push(&head, 15);
cout << "Count of prime nodes = " << countPrimeRecursive(head);
return 0;
}
|
Java
class Node {
int data;
Node next;
Node( int data)
{
this .data = data;
this .next = null ;
}
}
public class GFG {
static Node push(Node head, int newData)
{
Node newNode = new Node(newData);
newNode.next = head;
return newNode;
}
static boolean isPrime( int n)
{
if (n <= 1 )
return false ;
if (n <= 3 )
return true ;
if (n % 2 == 0 || n % 3 == 0 )
return false ;
for ( int i = 5 ; i * i <= n; i = i + 6 )
if (n % i == 0 || n % (i + 2 ) == 0 )
return false ;
return true ;
}
static int countPrimeRecursive(Node head)
{
if (head == null )
return 0 ;
int count = countPrimeRecursive(head.next);
if (isPrime(head.data))
count++;
return count;
}
public static void main(String[] args)
{
Node head = null ;
head = push(head, 17 );
head = push(head, 10 );
head = push(head, 6 );
head = push(head, 5 );
head = push(head, 15 );
System.out.println( "Count of prime nodes = "
+ countPrimeRecursive(head));
}
}
|
Python
class Node:
def __init__( self , data):
self .data = data
self . next = None
def push(head, new_data):
new_node = Node(new_data)
new_node. next = head
return new_node
def is_prime(n):
if n < = 1 :
return False
if n < = 3 :
return True
if n % 2 = = 0 or n % 3 = = 0 :
return False
i = 5
while i * i < = n:
if n % i = = 0 or n % (i + 2 ) = = 0 :
return False
i + = 6
return True
def count_prime_recursive(head):
if head is None :
return 0
count = count_prime_recursive(head. next )
if is_prime(head.data):
count + = 1
return count
if __name__ = = "__main__" :
head = None
head = push(head, 17 )
head = push(head, 10 )
head = push(head, 6 )
head = push(head, 5 )
head = push(head, 15 )
print ( "Count of prime nodes =" , count_prime_recursive(head))
|
C#
using System;
class Node
{
public int data;
public Node next;
public Node( int data)
{
this .data = data;
this .next = null ;
}
}
public class GFG
{
static Node Push(Node head, int newData)
{
Node newNode = new Node(newData);
newNode.next = head;
return newNode;
}
static bool IsPrime( int n)
{
if (n <= 1)
return false ;
if (n <= 3)
return true ;
if (n % 2 == 0 || n % 3 == 0)
return false ;
for ( int i = 5; i * i <= n; i += 6)
if (n % i == 0 || n % (i + 2) == 0)
return false ;
return true ;
}
static int CountPrimeRecursive(Node head)
{
if (head == null )
return 0;
int count = CountPrimeRecursive(head.next);
if (IsPrime(head.data))
count++;
return count;
}
public static void Main( string [] args)
{
Node head = null ;
head = Push(head, 17);
head = Push(head, 10);
head = Push(head, 6);
head = Push(head, 5);
head = Push(head, 15);
Console.WriteLine( "Count of prime nodes = " + CountPrimeRecursive(head));
}
}
|
Javascript
class Node {
constructor(data) {
this .data = data;
this .next = null ;
}
}
function push(head, new_data) {
let new_node = new Node(new_data);
new_node.next = head;
head = new_node;
return head;
}
function isPrime(n) {
if (n <= 1)
return false ;
if (n <= 3)
return true ;
if (n % 2 === 0 || n % 3 === 0)
return false ;
for (let i = 5; i * i <= n; i = i + 6)
if (n % i === 0 || n % (i + 2) === 0)
return false ;
return true ;
}
function countPrimeRecursive(head) {
if (head === null )
return 0;
let count = countPrimeRecursive(head.next);
if (isPrime(head.data))
count++;
return count;
}
let head = null ;
head = push(head, 17);
head = push(head, 10);
head = push(head, 6);
head = push(head, 5);
head = push(head, 15);
console.log( "Count of prime nodes =" , countPrimeRecursive(head));
|
Output
Count of prime nodes = 2
Time Complexity: O(N), where N is the number of nodes in the linked list.
Space Complexity: O(N), where N is the number of nodes in the linked list. This is because we create a recursive call stack for each node.