Find the largest prime number in String
Given a string S, representing a large integer, the task is to return the largest-valued prime integer (as a string) that is a substring of the given string S.
Note: A substring is a contiguous sequence of characters within a string. A null string (“”) is also a substring.
Examples:
Input: S = �”
Output: ????”
Explanation: The only substring ????” is the largest prime number.Input: S = �”
Output: �”
Explanation: The only substring �” is the largest prime number.Input: S = �”
Output: �”
Explanation: The only substring �” is the largest prime number.Input: S = �”
Output: “”
Explanation: There is no substring of a prime number.
Approach 1: (Bruteforce approach ) To solve the problem follow the below idea:
The idea is to check each and every substring by running two loops and checking whether the substring is prime or not and returning the largest prime number substring.
Below are the steps involved in the implementation of the code:
- Call the Function Find the largest prime by passing the string s as a parameter.
- Now iterate through each and every substring of the string and check whether it is prime or not.
- if is it prime check for the largest prime previous by taking an extra variable.
- Return the integer value of the largest substring in to_string format.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <cmath> #include <iostream> #include <string> using namespace std; // Function to check whether substring // is prime or not bool is_prime( int n) { if (n <= 1) return false ; for ( int i = 2; i <= sqrt (n); i++) { if (n % i == 0) return false ; } return true ; } // Function to find largest value prime // substring string find_largest_prime(string s) { int largest_prime = 0; // Start Iterating for ( int i = 0; i < s.length(); i++) { for ( int j = i + 1; j <= s.length(); j++) { string substring = s.substr(i, j - i); if (substring.find_first_not_of( "0123456789" ) == string::npos && is_prime(stoi(substring))) { largest_prime = max(largest_prime, stoi(substring)); } } } if (largest_prime < 0) return " " ; else return to_string(largest_prime); } // Driver Code int main() { string s; s = "132346" ; // Function call string largest_prime = find_largest_prime(s); cout << largest_prime << endl; return 0; } |
Java
// Java code for the above approach import java.util.*; public class GFG { // Function to check whether substring is prime or not static boolean isPrime( int n) { if (n <= 1 ) return false ; for ( int i = 2 ; i <= Math.sqrt(n); i++) { if (n % i == 0 ) return false ; } return true ; } // Function to find largest value prime substring static String findLargestPrime(String s) { int largestPrime = 0 ; // Start iterating for ( int i = 0 ; i < s.length(); i++) { for ( int j = i + 1 ; j <= s.length(); j++) { String substring = s.substring(i, j); if (substring.matches( "[0-9]+" ) && isPrime( Integer.parseInt(substring))) { largestPrime = Math.max( largestPrime, Integer.parseInt(substring)); } } } if (largestPrime < 0 ) return " " ; else return String.valueOf(largestPrime); } // Driver code public static void main(String[] args) { String s = "132346" ; // Function call String largestPrime = findLargestPrime(s); System.out.println(largestPrime); } } // This code is contributed by Susobhan Akhuli |
Python3
# Python code for the above approach: import math # Function to check whether substring is prime or not def is_prime(n): if n < = 1 : return False for i in range ( 2 , int (math.sqrt(n)) + 1 ): if n % i = = 0 : return False return True # Function to find largest value prime substring def find_largest_prime(s): largest_prime = 0 # Start Iterating for i in range ( len (s)): for j in range (i + 1 , len (s) + 1 ): substring = s[i:j] if substring.isdigit() and is_prime( int (substring)): largest_prime = max (largest_prime, int (substring)) if largest_prime < 0 : return " " else : return str (largest_prime) # Driver Code if __name__ = = "__main__" : s = "132346" # Function call largest_prime = find_largest_prime(s) print (largest_prime) |
C#
// C# code for the above approach using System; using System.Linq; public class GFG { // Function to check whether substring // is prime or not static bool IsPrime( int n) { if (n <= 1) return false ; for ( int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) return false ; } return true ; } // Function to find the largest value prime // substring static string FindLargestPrime( string s) { int largestPrime = 0; // Start Iterating for ( int i = 0; i < s.Length; i++) { for ( int j = i + 1; j <= s.Length; j++) { string substring = s.Substring(i, j - i); if (substring.All( char .IsDigit) && IsPrime( int .Parse(substring))) { largestPrime = Math.Max( largestPrime, int .Parse(substring)); } } } if (largestPrime < 0) return " " ; else return largestPrime.ToString(); } // Driver Code public static void Main() { string s = "132346" ; // Function call string largestPrime = FindLargestPrime(s); Console.WriteLine(largestPrime); } } // This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript code for the above approach // Function to check whether a number is prime or not function isPrime(n) { if (n <= 1) { return false ; } for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i === 0) { return false ; } } return true ; } // Function to find the largest value prime substring function findLargestPrime(s) { let largestPrime = 0; // Start iterating for (let i = 0; i < s.length; i++) { for (let j = i + 1; j <= s.length; j++) { let substring = s.substring(i, j); if (/^\d+$/.test(substring) && isPrime(parseInt(substring))) { largestPrime = Math.max(largestPrime, parseInt(substring)); } } } if (largestPrime < 0) { return " " ; } else { return largestPrime.toString(); } } // Driver Code let s = "132346" ; // Function call let largestPrime = findLargestPrime(s); console.log(largestPrime); // This code is contributed by Susobhan Akhuli |
23
Time Complexity: O(N^3)* O(log (N)), where N is the length of the string.
Auxiliary Space: O(1).
Approach 2: To solve the problem follow the below idea:
The idea is to genrate all prime numbers upto the maximum substring number present in string.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to genrate all prime number void genratePrimes( bool isPrime[], int n) { for ( int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a prime if (isPrime[p] == true ) { // Update all multiples of p greater than or // equal to the square of it numbers which are // multiple of p and are less than p^2 are // already been marked. for ( int i = p * p; i <= n; i += p) isPrime[i] = false ; } } } // Function to find largest value prime // substring string find_largest_prime(string s, bool isPrime[]) { int largest_prime = 0; // Start Iterating for ( int i = 0; i < s.length(); i++) { // using temp variable to store substring int temp=0; for ( int j = i; j < s.length(); j++) { temp = temp * 10 + (s[j] - '0' ); // check wheather temp is prime or not if (isPrime[temp]) largest_prime = max(largest_prime, temp); } } if (largest_prime < 0) return " " ; else return to_string(largest_prime); } // Driver Code int main() { string s; s = "132346" ; int n = stoi(s); // Create a boolean array "isPrime[0..n]" and initialize // all entries it as true. A value in isPrime[i] will // finally be false if i is Not a prime, else true. bool isPrime[n + 1]; memset (isPrime, true , sizeof (isPrime)); // Genrate all primes numbers upto max substring number // in string s genratePrimes(isPrime, n); // Function call for largest prime string largest_prime = find_largest_prime(s, isPrime); cout << largest_prime << endl; return 0; } |
Java
// Java code for the above approach import java.util.Arrays; public class GFG { // Function to generate all prime numbers static void generatePrimes( boolean isPrime[], int n) { for ( int p = 2 ; p * p <= n; p++) { // If isPrime[p] is not changed, then it is a // prime if (isPrime[p]) { // Update all multiples of p greater than or // equal to the square of it; numbers which // are multiples of p and are less than p^2 // are already marked. for ( int i = p * p; i <= n; i += p) isPrime[i] = false ; } } } // Function to find the largest value prime // substring static String findLargestPrime(String s, boolean isPrime[]) { int largestPrime = 0 ; // Start Iterating for ( int i = 0 ; i < s.length(); i++) { // Using temp variable to store substring int temp = 0 ; for ( int j = i; j < s.length(); j++) { temp = temp * 10 + (s.charAt(j) - '0' ); // Check whether temp is prime or not if (isPrime[temp]) largestPrime = Math.max(largestPrime, temp); } } if (largestPrime < 0 ) return " " ; else return Integer.toString(largestPrime); } // Driver Code public static void main(String[] args) { String s = "132346" ; int n = Integer.parseInt(s); // Create a boolean array "isPrime[0..n]" and // initialize all entries as true. A value in // isPrime[i] will finally be false if i is not a // prime, else true. boolean [] isPrime = new boolean [n + 1 ]; Arrays.fill(isPrime, true ); // Generate all prime numbers up to max substring // number in string s generatePrimes(isPrime, n); // Function call for the largest prime String largestPrime = findLargestPrime(s, isPrime); System.out.println(largestPrime); } } // This code is contributed by Susobhan Akhuli |
Python3
# Python code for the above approach # Function to generate all prime numbers up to n def generate_primes(n): is_prime = [ True ] * (n + 1 ) p = 2 while p * p < = n: if is_prime[p]: for i in range (p * p, n + 1 , p): is_prime[i] = False p + = 1 return is_prime # Function to find the largest prime substring def find_largest_prime(s, is_prime): largest_prime = 0 # Start iterating through the string for i in range ( len (s)): temp = 0 for j in range (i, len (s)): temp = temp * 10 + int (s[j]) # Check whether temp is prime or not if is_prime[temp]: largest_prime = max (largest_prime, temp) if largest_prime < 0 : return " " else : return str (largest_prime) # Driver Code if __name__ = = "__main__" : s = "132346" n = int (s) # Create a boolean array "is_prime[0..n]" and initialize # all entries it as true. A value in is_prime[i] will # finally be False if i is not a prime, else True. is_prime = generate_primes(n) # Function call for finding the largest prime substring largest_prime = find_largest_prime(s, is_prime) print (largest_prime) # This code is contributed by Susobhan Akhuli |
C#
// C# code for the above approach using System; public class GFG { // Function to genrate all prime number static void genratePrimes( bool [] isPrime, int n) { for ( int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a // prime if (isPrime[p] == true ) { // Update all multiples of p greater than or // equal to the square of it numbers which // are multiple of p and are less than p^2 // are already been marked. for ( int i = p * p; i <= n; i += p) { isPrime[i] = false ; } } } } // Function to find largest value prime substring static string find_largest_prime( string s, bool [] isPrime) { int largest_prime = 0; // Start Iterating for ( int i = 0; i < s.Length; i++) { // using temp variable to store substring int temp = 0; for ( int j = i; j < s.Length; j++) { temp = temp * 10 + (s[j] - '0' ); // check wheather temp is prime or not if (isPrime[temp]) { largest_prime = Math.Max(largest_prime, temp); } } } if (largest_prime < 0) { return " " ; } else { return largest_prime.ToString(); } } // Driver Code static void Main() { string s; s = "132346" ; int n = int .Parse(s); // Create a boolean array "isPrime[0..n]" and // initialize all entries it as true. A value in // isPrime[i] will finally be false if i is Not a // prime, else true. bool [] isPrime = new bool [n + 1]; for ( int i = 0; i <= n; i++) { isPrime[i] = true ; } // Genrate all primes numbers upto max substring // number in string s genratePrimes(isPrime, n); // Function call for largest prime string largest_prime = find_largest_prime(s, isPrime); Console.WriteLine(largest_prime); } } // This code is contributed by Susobhan Akhuli |
Javascript
<script> // JavaScript code for the above approach // Function to generate all prime numbers function generatePrimes(isPrime, n) { for (let p = 2; p * p <= n; p++) { // If isPrime[p] is true, then it is a prime if (isPrime[p] === true ) { // Update all multiples of p greater than or equal to p^2 // Numbers which are multiple of p and are less than p^2 are already marked for (let i = p * p; i <= n; i += p) { isPrime[i] = false ; } } } } // Function to find the largest value prime substring function findLargestPrime(s, isPrime) { let largestPrime = 0; // Start iterating for (let i = 0; i < s.length; i++) { // Using temp variable to store substring let temp = 0; for (let j = i; j < s.length; j++) { temp = temp * 10 + parseInt(s[j]); // Check whether temp is prime or not if (isPrime[temp]) { largestPrime = Math.max(largestPrime, temp); } } } if (largestPrime < 0) { return " " ; } else { return largestPrime.toString(); } } let s = "132346" ; let n = parseInt(s); // Create a boolean array "isPrime[0..n]" and initialize all entries as true // A value in isPrime[i] will finally be false if i is not a prime, else true let isPrime = new Array(n + 1).fill( true ); // Generate all prime numbers up to the maximum substring number in string s generatePrimes(isPrime, n); // Function call for the largest prime let largestPrime = findLargestPrime(s, isPrime); document.write(largestPrime); // This code is contributed by Susobhan Akhuli </script> |
23
Time Complexity: O(N^2) + O(N*log(log(N))) ≈ O(N^2), N*log(log(N)) is used for generating all prime numbers to where N is the length of the string.
Auxiliary Space: O(N)
Contact Us