Largest number less than N whose each digit is prime number | C ++ program to find the largest number smaller than N whose all digits are prime . ; Number is given as string . ; We stop traversing digits , once it become smaller than current number . For that purpose we use small variable . ; Array indicating if index i ( represents a digit ) is prime or not . ; Store largest ; If there is only one character , return the largest prime less than the number ; If number starts with 1 , return number consisting of 7 ; Traversing each digit from right to left Continue traversing till the number we are forming will become less . ; If digit is prime , copy it simply . ; If not prime , copy the largest prime less than current number ; If not prime , and there is no largest prime less than current prime ; 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 ; If the given number is itself a prime . ; Make last digit as highest prime less than given digit . ; If there is no highest prime less than current digit . ; Once one digit become less than any digit of input replace 7 ( largest 1 digit prime ) till the end of digits of number ; If number include 0 in the beginning , ignore them . Case like 2200 ; Driver Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; char * PrimeDigitNumber ( char N [ ] , int size ) { char * ans = ( char * ) malloc ( size * sizeof ( char ) ) ; int ns = 0 ; int small = 0 ; int i ; int p [ ] = { 0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 0 } ; int prevprime [ ] = { 0 , 0 , 0 , 2 , 3 , 3 , 5 , 5 , 7 , 7 } ; if ( size == 1 ) { ans [ 0 ] = prevprime [ N [ 0 ] - '0' ] + '0' ; ans [ 1 ] = ' \0' ; return ans ; } if ( N [ 0 ] == '1' ) { for ( int i = 0 ; i < size - 1 ; i ++ ) ans [ i ] = '7' ; ans [ size - 1 ] = ' \0' ; return ans ; } for ( i = 0 ; i < size && small == 0 ; i ++ ) { if ( p [ N [ i ] - '0' ] == 1 ) { ans [ ns ++ ] = N [ i ] ; } else { if ( p [ N [ i ] - '0' ] == 0 && prevprime [ N [ i ] - '0' ] != 0 ) { ans [ ns ++ ] = prevprime [ N [ i ] - '0' ] + '0' ; small = 1 ; } else if ( p [ N [ i ] - '0' ] == 0 && prevprime [ N [ i ] - '0' ] == 0 ) { int j = i ; 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 ( small == 0 ) { if ( prevprime [ N [ size - 1 ] - '0' ] + '0' != '0' ) ans [ size - 1 ] = prevprime [ N [ size - 1 ] - '0' ] + '0' ; 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 -- ; } } } for ( ; ns < size ; ns ++ ) ans [ ns ] = '7' ; ans [ ns ] = ' \0' ; int k = 0 ; while ( ans [ k ] == '0' ) k ++ ; return ans + k ; } int main ( ) { char N [ ] = "1000" ; int size = strlen ( N ) ; cout << PrimeDigitNumber ( N , size ) << endl ; return 0 ; }