1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach(Maths)
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
5.
Key takeaways
Last Updated: Mar 27, 2024

# Find Any Prime Number P contains given Number N.

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

1. Start Iterating from the Given number N using for loop.
2. Check for each number if it is prime or not.
3. 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.
4. 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;
}

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

Output:

``421``

#### Complexity Analysis

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

Explanation: P is the required Prime Number.

Space ComplexityO(1)

Explanation: No extra Space is required.

## Optimized Approach(Maths)

We will use the fact that between any two consecutive primes up to 10^12, there are at most 464 non-prime numbers. We will multiply our current number by 1000, start traversing from this new number and check each number; if it is prime, we will print it. We can easily see that the number we are printing will always contain the number N because only the last three digits of this new number will be changed, and the original number N will be present.

### Steps of Algorithm

1. Multiply the given number N by 1000.
2. Start iterating from this number and check if it is prime or not.
3. If it is a prime number, print the number; it will be our required answer.
4. We can easily see that it always contains the number N, as only the last three digits will be changed.

### Implementation in C++

``````// c++ program to find the prime number p, containing n in it.
#include<bits/stdc++.h>
using namespace std;
// checking the number is prime or not
bool isPrime(int n){
for(int i=2;i*i<=n;i++){
if(n%i==0)
// if not prime return false
return false;
}
// if the number is prime, return true
return true;
}
int main(){
// given number n
int n = 42;
// multiply n by 1000
n = n*1000;
// starting traversing from number n+1
for(int i=n+1;;i++){
// if the number is prime, then print the number
// and break the loop
if(isPrime(i)){
cout << i << endl;
break;
}
}
return 0;
}``````

Output:

``````42013
Explanation: Since we will start checking from 42*1000 = 42000, the first prime number after that is 42013. ``````

#### Complexity Analysis

Time Complexity: O(sqrt(N*1000) * 464)

Explanation: Since We will start iterating from the number N*1000, we can maximum go to (N*1000 + 464).

Space ComplexityO(1)

Explanation: No extra Space is required.

Also check out - Substr C++

Q1. Why 1 is not considered a prime number?

Ans. According to the definition of the prime number, a prime number should exactly have 2 factors, i.e., 1 and number itself. Since 1 has only one factor, it is not a prime number.

Q2. What is the highest prime factor of a given number N?

Ans. If the number N is prime itself, then it will be itself the highest prime factor; otherwise, the Highest prime factor of non-prime Number N will be less than or equal to sqrt(N).

Q3. How to find the total count of factors if we are given prime factors of a given number N?

Ans. Let say we have 40, then its prime factors are 2*2*2*5 = 2^3 * 5^1 * 7^0 * 11^0 ……

Total Factors = (3+1)*(1+1)*(0+1)*(0+1)......... = 8 .

So total factors are equal to the product of the highest power of prime factors + 1.

## Key takeaways

In this article, we discussed the problem of finding the Prime Number P containing given Number N. We discussed the two approaches, i.e., brute force and optimized approach using maths. We hope you understand the problem and solution properly. Now you can do more similar questions.

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free!