# 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;
};

{
Node* new_node = new Node;
new_node->data = new_data;
}

// 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;
}

{

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

// Driver program
int main()
{

// Push elements into linked list
// 1 -> 3 -> 19 -> 5 -> 6 -> 10 -> 17

// Call the function to print require answer
cout << "Prime nodes are: ";
```Output: