Given a very large number N (1 <= number of digit in N <= 105). The task is find the largest number X such that X < N and each digit of X is prime number.
Examples:
Input : N = 1000
Output : 777
777 is the largest number less than
1000 which have each digit as prime.
Input : N = 11
Output : 7
Approach 1: The idea is to traverse from leftmost digit of the number N to rightmost digit of N. Check if the current digit is prime or not. If it is prime, copy the digit to output number at corresponding digit position. If it is not prime, copy the largest prime number less than current digit.
Now consider if the current digit is ‘0’ or ‘1’. In that case copy ‘7’ to current digit position of output number. Also move to adjacent left digit of current digit and reduce it to largest prime number less than it.
Once we reduce any digit to largest prime number less than the digit, we copy ‘7’ to rest of the right digit in the output number.
Below is the implementation of this approach:
C++
// C++ program to find the largest number smaller// than N whose all digits are prime.#include <bits/stdc++.h>using namespace std;// Number is given as string.char* PrimeDigitNumber(char N[], int size){ char* ans = (char*)malloc(size * sizeof(char)); int ns = 0; // We stop traversing digits, once it become // smaller than current number. // For that purpose we use small variable. int small = 0; int i; // Array indicating if index i (represents a // digit) is prime or not. int p[] = { 0, 0, 1, 1, 0, 1, 0, 1, 0, 0 }; // Store largest int prevprime[] = { 0, 0, 0, 2, 3, 3, 5, 5, 7, 7 }; // If there is only one character, return // the largest prime less than the number if (size == 1) { ans[0] = prevprime[N[0] - '0'] + '0'; ans[1] = '\0'; return ans; } // If number starts with 1, return number // consisting of 7 if (N[0] == '1') { for (int i = 0; i < size - 1; i++) ans[i] = '7'; ans[size - 1] = '\0'; return ans; } // Traversing each digit from right to left // Continue traversing till the number we // are forming will become less. for (i = 0; i < size && small == 0; i++) { // If digit is prime, copy it simply. if (p[N[i] - '0'] == 1) { ans[ns++] = N[i]; } else { // If not prime, copy the largest prime // less than current number if (p[N[i] - '0'] == 0 && prevprime[N[i] - '0'] != 0) { ans[ns++] = prevprime[N[i] - '0'] + '0'; small = 1; } // If not prime, and there is no largest // prime less than current prime else if (p[N[i] - '0'] == 0 && prevprime[N[i] - '0'] == 0) { int j = i; // Make current digit as 7 // Go left of the digit and make it largest // prime less than number. Continue do that // until we found a digit which has some // largest prime less than it while (j > 0 && p[N[j] - '0'] == 0 && prevprime[N[j] - '0'] == 0) { ans[j] = N[j] = '7'; N[j - 1] = prevprime[N[j - 1] - '0'] + '0'; ans[j - 1] = N[j - 1]; small = 1; j--; } i = ns; } } } // If the given number is itself a prime. if (small == 0) { // Make last digit as highest prime less // than given digit. if (prevprime[N[size - 1] - '0'] + '0' != '0') ans[size - 1] = prevprime[N[size - 1] - '0'] + '0'; // If there is no highest prime less than // current digit. else { int j = size - 1; while (j > 0 && prevprime[N[j] - '0'] == 0) { ans[j] = N[j] = '7'; N[j - 1] = prevprime[N[j - 1] - '0'] + '0'; ans[j - 1] = N[j - 1]; small = 1; j--; } } } // Once one digit become less than any digit of input // replace 7 (largest 1 digit prime) till the end of // digits of number for (; ns < size; ns++) ans[ns] = '7'; ans[ns] = '\0'; // If number include 0 in the beginning, ignore // them. Case like 2200 int k = 0; while (ans[k] == '0') k++; return ans + k;}// Driver Programint main(){ char N[] = "1000"; int size = strlen(N); cout << PrimeDigitNumber(N, size) << endl; return 0;} |
Java
// Java program to find the largest number smaller// than N whose all digits are prime.import java.io.*;class GFG { // Number is given as string. static char[] PrimeDigitNumber(char N[], int size) { char[] ans = new char[size]; int ns = 0; // We stop traversing digits, once it become // smaller than current number. // For that purpose we use small variable. int small = 0; int i; // Array indicating if index i (represents a // digit) is prime or not. int p[] = { 0, 0, 1, 1, 0, 1, 0, 1, 0, 0 }; // Store largest int prevprime[] = { 0, 0, 0, 2, 3, 3, 5, 5, 7, 7 }; // If there is only one character, return // the largest prime less than the number if (size == 1) { ans[0] = (char)(prevprime[N[0] - '0'] + '0'); ans[1] = '\0'; return ans; } // If number starts with 1, return number // consisting of 7 if (N[0] == '1') { for (i = 0; i < size - 1; i++) ans[i] = '7'; ans[size - 1] = '\0'; return ans; } // Traversing each digit from right to left // Continue traversing till the number we // are forming will become less. for (i = 0; i < size && small == 0; i++) { // If digit is prime, copy it simply. if (p[N[i] - '0'] == 1) { ans[ns++] = N[i]; } else { // If not prime, copy the largest prime // less than current number if (p[N[i] - '0'] == 0 && prevprime[N[i] - '0'] != 0) { ans[ns++] = (char)(prevprime[N[i] - '0'] + '0'); small = 1; } // If not prime, and there is no largest // prime less than current prime else if (p[N[i] - '0'] == 0 && prevprime[N[i] - '0'] == 0) { int j = i; // Make current digit as 7 // Go left of the digit and make it largest // prime less than number. Continue do that // until we found a digit which has some // largest prime less than it while (j > 0 && p[N[j] - '0'] == 0 && prevprime[N[j] - '0'] == 0) { ans[j] = N[j] = '7'; N[j - 1] = (char)(prevprime[N[j - 1] - '0'] + '0'); ans[j - 1] = N[j - 1]; small = 1; j--; } i = ns; } } } // If the given number is itself a prime. if (small == 0) { // Make last digit as highest prime less // than given digit. if (prevprime[N[size - 1] - '0'] + '0' != '0') ans[size - 1] = (char)(prevprime[N[size - 1] - '0'] + '0'); // If there is no highest prime less than // current digit. else { int j = size - 1; while (j > 0 && prevprime[N[j] - '0'] == 0) { ans[j] = N[j] = '7'; N[j - 1] = (char)(prevprime[N[j - 1] - '0'] + '0'); ans[j - 1] = N[j - 1]; small = 1; j--; } } } // Once one digit become less than any digit of input // replace 7 (largest 1 digit prime) till the end of // digits of number for (; ns < size; ns++) ans[ns] = '7'; ans[ns] = '\0'; // If number include 0 in the beginning, ignore // them. Case like 2200 int k = 0; while (ans[k] == '0') k++; return ans; } // Driver Program public static void main (String[] args) { char[] N= "1000".toCharArray(); int size=N.length; System.out.println(PrimeDigitNumber(N, size)); }}// This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 program to find the largest number smaller# than N whose all digits are prime.# Number is given as string.def PrimeDigitNumber(N, size): ans = [""]*size ns = 0; # We stop traversing digits, once it become # smaller than current number. # For that purpose we use small variable. small = 0; # Array indicating if index i (represents a # digit) is prime or not. p = [ 0, 0, 1, 1, 0, 1, 0, 1, 0, 0 ] # Store largest prevprime = [ 0, 0, 0, 2, 3, 3, 5, 5, 7, 7 ] # If there is only one character, return # the largest prime less than the number if (size == 1): ans[0] = prevprime[ord(N[0]) - ord('0')] + ord('0'); ans[1] = ''; return ''.join(ans); # If number starts with 1, return number # consisting of 7 if (N[0] == '1'): for i in range(size - 1): ans[i] = '7' ans[size - 1] = ''; return ''.join(ans) # Traversing each digit from right to left # Continue traversing till the number we # are forming will become less. i = 0 while (i < size and small == 0): # If digit is prime, copy it simply. if (p[ord(N[i]) - ord('0')] == 1): ans[ns] = N[i] ns += 1 else: # If not prime, copy the largest prime # less than current number if (p[ord(N[i]) - ord('0')] == 0 and prevprime[ord(N[i]) - ord('0')] != 0): ans[ns] = prevprime[ord(N[i]) - ord('0')] + ord('0'); small = 1 ns += 1 # If not prime, and there is no largest # prime less than current prime elif (p[ord(N[i]) - ord('0')] == 0 and prevprime[ord(N[i]) - ord('0')] == 0): j = i; # Make current digit as 7 # Go left of the digit and make it largest # prime less than number. Continue do that # until we found a digit which has some # largest prime less than it while (j > 0 and p[ord(N[j]) - ord('0')] == 0 and prevprime[ord(N[j]) - ord('0')] == 0): ans[j] = N[j] = '7'; N[j - 1] = prevprime[ord(N[j - 1]) - ord('0')] + ord('0'); ans[j - 1] = N[j - 1]; small = 1; j -= 1 i = ns i += 1 # If the given number is itself a prime. if (small == 0): # Make last digit as highest prime less # than given digit. if (prevprime[ord(N[size - 1]) - ord('0')] + ord('0') != ord('0')): ans[size - 1] = prevprime[ord(N[size - 1]) - ord('0')] + ord('0'); # If there is no highest prime less than # current digit. else : j = size - 1; while (j > 0 and prevprime[ord(N[j]) - ord('0')] == 0): ans[j] = N[j] = '7'; N[j - 1] = prevprime[ord(N[j - 1]) - ord('0')] + ord('0'); ans[j - 1] = N[j - 1]; small = 1; j -= 1 # Once one digit become less than any digit of input # replace 7 (largest 1 digit prime) till the end of # digits of number while(ns < size): ans[ns] = '7' ns += 1 ans[ns] = ''; # If number include 0 in the beginning, ignore # them. Case like 2200 k = 0; while (ans[k] == '0'): k += 1 return (ans + k)# Driver Programif __name__ == "__main__": N = "1000"; size = len(N); print(PrimeDigitNumber(N, size)) # This code is contributed by chitranayal. |
C#
// C# program to find the largest number smaller// than N whose all digits are prime.using System;class GFG{ // Number is given as string.static char[] PrimeDigitNumber(char[] N, int size){ char[] ans = new char[size]; int ns = 0; // We stop traversing digits, once it become // smaller than current number. // For that purpose we use small variable. int small = 0; int i; // Array indicating if index i (represents a // digit) is prime or not. int[] p = { 0, 0, 1, 1, 0, 1, 0, 1, 0, 0 }; // Store largest int[] prevprime = { 0, 0, 0, 2, 3, 3, 5, 5, 7, 7 }; // If there is only one character, return // the largest prime less than the number if (size == 1) { ans[0] = (char)(prevprime[N[0] - '0'] + '0'); ans[1] = '\0'; return ans; } // If number starts with 1, return number // consisting of 7 if (N[0] == '1') { for (i = 0; i < size - 1; i++) ans[i] = '7'; ans[size - 1] = '\0'; return ans; } // Traversing each digit from right to left // Continue traversing till the number we // are forming will become less. for(i = 0; i < size && small == 0; i++) { // If digit is prime, copy it simply. if (p[N[i] - '0'] == 1) { ans[ns++] = N[i]; } else { // If not prime, copy the largest prime // less than current number if (p[N[i] - '0'] == 0 && prevprime[N[i] - '0'] != 0) { ans[ns++] = (char)(prevprime[N[i] - '0'] + '0'); small = 1; } // If not prime, and there is no largest // prime less than current prime else if (p[N[i] - '0'] == 0 && prevprime[N[i] - '0'] == 0) { int j = i; // Make current digit as 7 // Go left of the digit and make it largest // prime less than number. Continue do that // until we found a digit which has some // largest prime less than it while (j > 0 && p[N[j] - '0'] == 0 && prevprime[N[j] - '0'] == 0) { ans[j] = N[j] = '7'; N[j - 1] = (char)( prevprime[N[j - 1] - '0'] + '0'); ans[j - 1] = N[j - 1]; small = 1; j--; } i = ns; } } } // If the given number is itself a prime. if (small == 0) { // Make last digit as highest prime less // than given digit. if (prevprime[N[size - 1] - '0'] + '0' != '0') ans[size - 1] = (char)( prevprime[N[size - 1] - '0'] + '0'); // If there is no highest prime less than // current digit. else { int j = size - 1; while (j > 0 && prevprime[N[j] - '0'] == 0) { ans[j] = N[j] = '7'; N[j - 1] = (char)( prevprime[N[j - 1] - '0'] + '0'); ans[j - 1] = N[j - 1]; small = 1; j--; } } } // Once one digit become less than any digit of input // replace 7 (largest 1 digit prime) till the end of // digits of number for(; ns < size; ns++) ans[ns] = '7'; ans[ns] = '\0'; // If number include 0 in the beginning, ignore // them. Case like 2200 int k = 0; while (ans[k] == '0') k++; return ans;}// Driver Codestatic public void Main(){ char[] N = "1000".ToCharArray(); int size = N.Length; Console.WriteLine(PrimeDigitNumber(N, size));}}// This code is contributed by rag2127 |
Javascript
<script>// Javascript program to find the largest number smaller// than N whose all digits are prime.// Number is given as string.function PrimeDigitNumber(N,size){ let ans = new Array(size); let ns = 0; // We stop traversing digits, once it become // smaller than current number. // For that purpose we use small variable. let small = 0; let i; // Array indicating if index i (represents a // digit) is prime or not. let p = [ 0, 0, 1, 1, 0, 1, 0, 1, 0, 0 ]; // Store largest let prevprime = [ 0, 0, 0, 2, 3, 3, 5, 5, 7, 7 ]; // If there is only one character, return // the largest prime less than the number if (size == 1) { ans[0] = String.fromCharCode(prevprime[N[0].charCodeAt(0) - '0'.charCodeAt(0)] + '0'.charCodeAt(0)); ans[1] = '\0'; return ans; } // If number starts with 1, return number // consisting of 7 if (N[0] == '1') { for (i = 0; i < size - 1; i++) ans[i] = '7'; ans[size - 1] = '\0'; return ans; } // Traversing each digit from right to left // Continue traversing till the number we // are forming will become less. for (i = 0; i < size && small == 0; i++) { // If digit is prime, copy it simply. if (p[N[i].charCodeAt(0) - '0'.charCodeAt(0)] == 1) { ans[ns++] = N[i]; } else { // If not prime, copy the largest prime // less than current number if (p[N[i] - '0'] == 0 && prevprime[N[i].charCodeAt(0) - '0'.charCodeAt(0)] != 0) { ans[ns++] = String.fromCharCode(prevprime[N[i].charCodeAt(0) - '0'.charCodeAt(0)] + '0'.charCodeAt(0)); small = 1; } // If not prime, and there is no largest // prime less than current prime else if (p[N[i].charCodeAt(0) - '0'.charCodeAt(0)] == 0 && prevprime[N[i].charCodeAt(0) - '0'.charCodeAt(0)] == 0) { let j = i; // Make current digit as 7 // Go left of the digit and make it largest // prime less than number. Continue do that // until we found a digit which has some // largest prime less than it while (j > 0 && p[N[j].charCodeAt(0) - '0'.charCodeAt(0)] == 0 && prevprime[N[j].charCodeAt(0) - '0'.charCodeAt(0)] == 0) { ans[j] = N[j] = '7'; N[j - 1] = String.fromCharCode(prevprime[N[j - 1].charCodeAt(0) - '0'.charCodeAt(0)] + '0'.charCodeAt(0)); ans[j - 1] = N[j - 1]; small = 1; j--; } i = ns; } } } // If the given number is itself a prime. if (small == 0) { // Make last digit as highest prime less // than given digit. if (prevprime[N[size - 1].charCodeAt(0) - '0'.charCodeAt(0)] + '0'.charCodeAt(0) != '0'.charCodeAt(0)) ans[size - 1] = String.fromCharCode(prevprime[N[size - 1].charCodeAt(0) - '0'.charCodeAt(0)] + '0'.charCodeAt(0)); // If there is no highest prime less than // current digit. else { let j = size - 1; while (j > 0 && prevprime[N[j].charCodeAt(0) - '0'.charCodeAt(0)] == 0) { ans[j] = N[j] = '7'; N[j - 1] = String.fromCharCode(prevprime[N[j - 1].charCodeAt(0) - '0'.charCodeAt(0)] + '0'.charCodeAt(0)); ans[j - 1] = N[j - 1]; small = 1; j--; } } } // Once one digit become less than any digit of input // replace 7 (largest 1 digit prime) till the end of // digits of number for (; ns < size; ns++) ans[ns] = '7'; ans[ns] = '\0'; // If number include 0 in the beginning, ignore // them. Case like 2200 let k = 0; while (ans[k] == '0') k++; return ans.join("");}// Driver Programlet N= "1000".split("");let size=N.length;document.write(PrimeDigitNumber(N, size).join(""));// This code is contributed by ab2127</script> |
Output:
777
The time complexity of this algorithm is O(n), where n is the number of digits in the given number.
The space complexity of this algorithm is O(n), where n is the number of digits in the given number. This is because we are using an array of size n to store the result.
Approach 2:
Algorithm steps:
- Define a function isPrime that takes an integer n as input and checks if it is a prime number or not by iterating from 2 to the square root of n and checking if n is divisible by i.
- Define a function largestPrimeDigitNumber that takes a string N as input.
- Convert the string N to an integer n using stoi.
- Iterate from n to 1:
a. Convert n to a string s using to_string.
b. Iterate through each digit of s and check if it is a prime number using the isPrime function defined earlier.
c. If all digits are prime, return s as the largest prime digit number. - If no prime digit number is found in the range, return “-1”.
Below is the implementation of the above approach:
C++
//C++ code for the above approch#include <bits/stdc++.h>using namespace std;// function to check if a number is prime or notbool isPrime(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 the largest prime digit number less than or equal to Nstring largestPrimeDigitNumber(string N) { int n = stoi(N); while (n > 0) { string s = to_string(n); bool allPrime = true;\ for (int i = 0; i < s.length(); i++) { if (!isPrime(s[i] - '0')) { allPrime = false; break; } } if (allPrime) return s; n--; } return "-1"; }int main() { string N = "1000"; string ans = largestPrimeDigitNumber(N); cout << ans << endl; return 0; } |
Java
// Java code for above approachimport java.util.*;class GFG { // function to check if a number 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 the largest prime digit number less // than or equal to N static String largestPrimeDigitNumber(String N) { int n = Integer.parseInt(N); while (n > 0) { String s = Integer.toString(n); boolean allPrime = true; for (int i = 0; i < s.length(); i++) { if (!isPrime(s.charAt(i) - '0')) { allPrime = false; break; } } if (allPrime) return s; n--; } return "-1"; } public static void main(String[] args) { Scanner s = new Scanner(System.in); String N = "1000"; String ans = largestPrimeDigitNumber(N); System.out.println(ans); }} |
Python3
import math# Function to check if a number is prime or notdef 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 the largest prime digit number less than or equal to Ndef largest_prime_digit_number(N): n = int(N) while n > 0: s = str(n) all_prime = True for digit in s: if not is_prime(int(digit)): all_prime = False break if all_prime: return s n -= 1 return "-1"if __name__ == "__main__": N = "1000" ans = largest_prime_digit_number(N) print(ans) |
C#
using System;class GFG{ // Function to check if a number 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 prime digit number less // than or equal to N static string LargestPrimeDigitNumber(string N) { int n = int.Parse(N); while (n > 0) { string s = n.ToString(); bool allPrime = true; for (int i = 0; i < s.Length; i++) { if (!IsPrime(s[i] - '0')) { allPrime = false; break; } } if (allPrime) return s; n--; } return "-1"; } public static void Main() { string N = "1000"; string ans = LargestPrimeDigitNumber(N); Console.WriteLine(ans); }} |
Javascript
//Javascript code for the above approach// function to check if a number is prime or notfunction 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 prime digit number less than or // equal to Nfunction largestPrimeDigitNumber(N) { let n = Number(N); while (n > 0) { let s = String(n); let allPrime = true; for (let i = 0; i < s.length; i++) { if (!isPrime(s[i] - "0")) { allPrime = false; break; } } if (allPrime) return s; n--; } return "-1";}let N = "1000";let ans = largestPrimeDigitNumber(N);console.log(`${ans}`); |
Output:
777
Time complexity: O(N^2), where N is the value of the input string N, because the code iterates over all numbers less than or equal to N and checks the primality of each digit in each number.
Auxiliary Space: O(log N), because the code stores a string representation of each number less than or equal to N.
This article is contributed by Anuj Chauhan (anuj0503). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more inforation about the topic discussed above.
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!
