Wednesday, 27 Oct 2021

# Find a prime number S containing given number N in it

Given an integer N, find a prime number S such that all digits of N occur in a contiguous sequence. There may be multiple answers. Print any one of them.Example:Input: N = 42Output: 42013Explanation: 42013 is a prime and 42 occurs as a contiguous number in it. 15427 is also a correct answer.Input: N = 47Output: 47Explanation: 47 itself is a primeNaive Approach: Below steps can be followed:Iterate through all the numbers starting from NConvert every number into a string with to_string() functionCheck for the required substring using str.find() functionIf there is any number that has N as a substring and it is prime then return that numberTime Complexity: O(S), where S is the required prime numberEfficient Approach: Below steps can be followed:The fact can be used that a number with value upto 1e12, between two consecutive primes, there are at most 464 non-prime numbers.Extend the current number N by multiplying by 1000.After that iterate through the next numbers one by one and check each of them.If the number is prime then print that number.It is easy to see that the first condition will always follow as the digits except the last three will be N.Below is the implementation of the above approach:C++  #include using namespace std;  bool isPrime(long long N){    if (N == 1)        return false;    for (long long i = 2; i