Find Any Prime Number P contains given Number N.

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 Complexity: O(1)

Explanation: No extra Space is required. 

Also check out - Substr C++

Frequently asked questions

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! 

Thank you for reading. 

Until then, Keep Learning and Keep Coding.