小于N的最大数，其每个数字都是素数-yiteyi-C++库

考虑到一个非常大的数字 N （1<=N中的位数<=10） ^5. ).任务是找到最大的数字X，使X

null

例如：

Input : N = 1000Output : 777777 is the largest number less than1000 which have each digit as prime.Input : N = 11Output : 7

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

其思想是从数字N的最左边的数字遍历到N的最右边的数字。检查当前数字是否为素数。如果是素数，将数字复制到相应数字位置的输出数字。如果不是素数，复制小于当前数字的最大素数。

现在考虑当前数字是“0”还是“1”。在这种情况下，将“7”复制到输出编号的当前数字位置。也移动到当前数字的相邻左数位，并将其减少到小于它的最大素数。一旦我们将任何数字减少到小于该数字的最大素数，我们就将“7”复制到输出数字中右边的其余数字。

以下是该方法的实施情况：

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] =                                           ' '                                           ;                           
                                                         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] =                                           ' '                                           ;                           
             
                                                         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] =                                           ' '                                           ;                           
             
                                                         // If number include 0 in the beginning, ignore                           
                                                         // them. Case like 2200                           
                                                         int                                           k = 0;                           
                                                         while                                           (ans[k] ==                                           '0'                                           )                           
                                                         k++;                           
             
                                                         return                                           ans + k;                           
                             }                           
             
                             // Driver Program                           
                             int                                           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                                           ] =                                           ' '                                           ;                           
                                                         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                                           ] =                                           ' '                                           ;                           
             
                                                         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] =                                           ' '                                           ;                           
             
                                                         // 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 Program                           
                             if                                           __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] =                                           ' '                                           ;                           
                                                         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] =                                           ' '                                           ;                           
                                         
                                                         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] =                                           ' '                                           ;                           
                                         
                                                         // If number include 0 in the beginning, ignore                           
                                                         // them. Case like 2200                           
                                                         int                                           k = 0;                           
                                                         while                                           (ans[k] ==                                           '0'                                           )                           
                                                         k++;                           
                                         
                                                         return                                           ans;                           
                             }                           
             
                             // Driver Code                           
                             static                                           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] =                                           ' '                                           ;                           
                                                         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] =                                           ' '                                           ;                           
                                         
                                                         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] =                                           ' '                                           ;                           
                                         
                                                         // If number include 0 in the beginning, ignore                           
                                                         // them. Case like 2200                           
                                                         let k = 0;                           
                                                         while                                           (ans[k] ==                                           '0'                                           )                           
                                                         k++;                           
                                         
                                                         return                                           ans.join(                                           ""                                           );                           
                             }                           
             
                             // Driver Program                           
                             let N=                                           "1000"                                           .split(                                           ""                                           );                           
                             let size=N.length;                           
                             document.write(PrimeDigitNumber(N, size).join(                                           ""                                           ));                           
             
                             // This code is contributed by ab2127                           
                             </script>                           

输出：

本文由 Anuj Chauhan（anuj0503） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章