# 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 (6*k* + *i*) for some integer *k* and for *i* = −1, 0, 1, 2, 3, 4. 2 divides (6*k* + 0), (6*k* + 2), (6*k* + 4) and 3 divides (6*k* + 3). Therefore, every prime number greater than 3 can be represented in the form of 6*k* ± 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 🙂

## Leave a Reply