## Introduction

### Problem Statement

The problem states we have to find any prime number P containing the given number N. There can be multiples output possible; print any of them.

We will discuss the brute and optimized approach, along with their c++ code.

### Sample Examples

**Example 1:**

```
Input : N = 42
Output: 1423
Explanation:
1423 is a prime number, and it contains number 42 in it.
Other possible Prime Numbers: 421, 1427, 1429, and so on.
```

**Example 2:**

```
Input : N = 41
Output: 41011
Explanation:
41011 is a prime number, and it contains number 41 in it.
```

## Brute Force Approach

In the brute force approach, we can start iterating from Number N and check for each number if the given number is prime or not. If it is prime, we can check if it contains the given number N. If it has Number N, then it is our possible answer.

### Steps of Algorithm

- Start Iterating from the Given number N using for loop.
- Check for each number if it is prime or not.
- If it is prime, then convert this number into a string and check if the given number N is present as a substring or not.
- If N is present as a substring then, break the loop.

### Implementation in C++

```
// c++ program to find the prime number p, containing n in it.
#include <bits/stdc++.h>
using namespace std;
int isPrime(int n){
for(int i=2;i*i<=n;i++){
if(n%i==0)
return false;
}
return true;
}
int FindPrimeNumber(int n){
// start iterating from n
for(int i=n;;i++){
if(isPrime(i)){
string s = to_string(i);
string number = to_string(n);
if(s.find(number)<s.size()){
return i;
}
}
}
}
signed main(){
int n = 42;
cout << FindPrimeNumber(n) << endl;
}
```

**Output:**

`421`

#### Complexity Analysis

**Time Complexity: O(P*sqrt(P))**

Explanation: P is the required Prime Number.

**Space Complexity**: **O(1)**

Explanation: No extra Space is required.