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 = 42
Output: 42013
Explanation: 42013 is a prime and 42 occurs as a contiguous number in it. 15427 is also a correct answer.Input: N = 47
Output: 47
Explanation: 47 itself is a prime
Naive Approach: Below steps can be followed:
- Iterate through all the numbers starting from N
- Convert every number into a string with to_string() function
- Check for the required substring using str.find() function
- If there is any number that has N as a substring and it is prime then return that number
Time Complexity: O(S), where S is the required prime number
Efficient 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++
// C++ Implementation for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if a number is primebool isPrime(long long N){ if (N == 1) return false; for (long long i = 2; i <= sqrt(N); i++) // If N is divisible then its not a prime if (N % i == 0) return false; return true;}// Function to print a prime number// which has N as a substringlong long prime_substring_Number(long long N){ // Check for the base case if (N == 0) { return 103; // 103 is a prime } // multiply N by 10^3 // Check for numbers from // N*1000 to N*1000 + 464 N *= 1000; for (long long i = N; i < N + 465; i++) { if (isPrime(i)) { return i; } } return 0;}// Driver Codeint main(){ long N = 42; cout << prime_substring_Number(N);} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG {static boolean isPrime(long N){ if (N == 1) return false; for (long i = 2; i <= Math.sqrt(N); i++) // If N is divisible then its not a prime if (N % i == 0) return false; return true;} // Function to print a prime number// which has N as a substringstatic long prime_substring_Number(long N){ // Check for the base case if (N == 0) { return 103; // 103 is a prime } // multiply N by 10^3 // Check for numbers from // N*1000 to N*1000 + 464 N *= 1000; for (long i = N; i < N + 465; i++) { if (isPrime(i)) { return i; } } return 0;}// Driver Code public static void main(String[] args) { long N = 42; System.out.println(prime_substring_Number(N)); }}// This code is contributed by maddler. |
Python3
# python Implementation for the above approach# importing math libraryfrom math import *# Function to check if a number is primedef isPrime(N) : if N > 1: # Iterate from 2 to n / 2 for i in range(2, int(N/2)+1): # If num is divisible by any number between # 2 and n / 2, it is not prime if (N % i) == 0: return False else: return True else: return False # Function to print a prime number# which has N as a substringdef prime_substring_Number(N) : # Check for the base case if (N == 0) : return 103 # 103 is a prime # multiply N by 10^3 # Check for numbers from # N*1000 to N*1000 + 464 N =N * 1000 for i in range(N,N + 465): if (isPrime(i)) : return i return 0# Driver CodeN = 42print(prime_substring_Number(N))# This code is contributed by anudeep23042002. |
C#
// C# Implementation for the above approachusing System;class GFG { // Function to check if a number is prime static bool isPrime(long N) { if (N == 1) return false; for (long i = 2; i <= Math.Sqrt(N); i++) // If N is divisible then its not a prime if (N % i == 0) return false; return true; } // Function to print a prime number // which has N as a substring static long prime_substring_Number(long N) { // Check for the base case if (N == 0) { return 103; // 103 is a prime } // multiply N by 10^3 // Check for numbers from // N*1000 to N*1000 + 464 N *= 1000; for (long i = N; i < N + 465; i++) { if (isPrime(i)) { return i; } } return 0; } // Driver Code public static void Main() { long N = 42; Console.WriteLine(prime_substring_Number(N)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to check if a number is prime function isPrime(N) { if (N == 1) return false; for (let i = 2; i <= Math.sqrt(N); i++) // If N is divisible then its not a prime if (N % i == 0) return false; return true; } // Function to print a prime number // which has N as a substring function prime_substring_Number(N) { // Check for the base case if (N == 0) { return 103; // 103 is a prime } // multiply N by 10^3 // Check for numbers from // N*1000 to N*1000 + 464 N *= 1000; for (let i = N; i < N + 465; i++) { if (isPrime(i)) { return i; } } return 0; } // Driver Code let N = 42; document.write(prime_substring_Number(N));// This code is contributed by Potta Lokesh </script> |
Output
42013
Time Complexity: O(sqrt(N*1000)*300)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
