C++ Program to find all prime numbers in a Linked List

In this tutorial, we shall be printing all the prime numbers in a Linked List. Given a singly linked list, the aim is to print the nodes containing a prime number. A prime number is a positive number that has only two divisors 1 and itself.

Input: List = 15 -> 5 -> 16 -> 12 -> 17
Output: 5 17

Input: List = 1 -> 3 -> 19 -> 5 -> 6 -> 10 -> 17
Output: 3 19 5 17

We use an optimized school method to find if a node is a prime number. To check if n is a prime, generally we iterate from 2 to n-1 and check if it divides n. But in our algorithm, instead of iterating till n-1, we iterate till √n because a larger factor of n must have been a multiple of smaller factor.

All integers can be expressed in the form of (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, 4. 2 divides (6k + 0), (6k + 2), (6k + 4) and 3 divides (6k + 3). Therefore, every prime number greater than 3 can be represented in the form of 6k ± 1. We ignore 1 as it is not a prime number. We eliminate the multiples of 2 and 3 so that all the composite numbers below 25 are eliminated. For every number, we check if it is prime and return it.

Below is our complete given C++ Program to find all prime numbers in a Linked List:

// C++ implementation to find prime numbers in the singly linked list 
#include <bits/stdc++.h> 
using namespace std; 

// Node of the singly linked list 
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; 
} 

// Function to check if a number is prime 
int isPrime(int n) 
{ 
  // Corner cases 
  if ((n == 2) || (n == 3)) 
    return n;  
 
  if (n == 1 || n % 2 == 0 || n % 3 == 0) 
    return -1; 

  for (int i = 5; i * i <= n; i = i + 6) 
    if (n % i == 0 || n % (i + 2) == 0) 
      return -1; 

  return n; 
} 

 
void getPrime(Node** head_ref) 
{ 
  Node* ptr = *head_ref; 

  while(ptr != NULL) { 
    int p = isPrime(ptr->data);
      if (p != -1) { 
        cout << p << " ";
      }
      ptr = ptr->next; 
  }
} 

// Driver program 
int main() 
{ 
  // Empty Linked List 
  Node* head = NULL; 

  // Push elements into linked list 
  // 1 -> 3 -> 19 -> 5 -> 6 -> 10 -> 17 
  push(&head, 17); 
  push(&head, 10); 
  push(&head, 6); 
  push(&head, 5); 
  push(&head, 19);
  push(&head, 3);
  push(&head, 1); 

  // Call the function to print require answer 
  cout << "Prime nodes are: ";
  getPrime(&head); 

  return 0; 
} 

Output:
Prime nodes are: 3 19 5 17

From the output, we can say that we are successfully able to do our task.

I am Vamsi Krishna and You can find my posts here

Also Read: How to find all Prime numbers less than or equal to N by sieve of Eratosthenes in Python.

Thank You for Reading and Keep Learning 🙂