Número más grande con dígitos primos

Dado un valor entero enorme n, encuentre el valor entero mayor x tal que x <= n y todos los dígitos de x sean primos.
Ejemplos: 

Input : n = 45
Output : 37
37 is the largest number smaller than
or equal to with all prime digits.

Input : n = 1000
Output : 777

Input : n = 7721
Output : 7577

Input : n = 7221
Output : 5777

Sabemos que los dígitos primos son 2, 3, 5 y 7. Además, como tenemos que manipular cada dígito de un número muy grande, será más fácil si lo hacemos como una string. La idea principal es encontrar el primer dígito no primo y luego 
encontrar el primer dígito mayor que 2 a su izquierda. Ahora podemos reemplazar el dígito encontrado con el dígito primo que es justo menor que él. Si el dígito es 2, tenemos que borrarlo y reemplazar el siguiente dígito con 7. Después de esto, podemos reemplazar los dígitos restantes a su derecha por 7. A continuación se muestra
la implementación del algoritmo anterior: 

C++

// CPP program to find largest number smaller than
// equal to n with all prime digits.
#include <bits/stdc++.h>
using namespace std;
 
// check if character is prime
bool isPrime(char c)
{
    return (c == '2' || c == '3' || c == '5' || c == '7');
}
 
// replace with previous prime character
void decrease(string& s, int i)
{
    // if 2 erase s[i] and replace next with 7
    if (s[i] <= '2') {
        s.erase(i, 1);
        s[i] = '7';
    }
 
    else if (s[i] == '3')
        s[i] = '2';
    else if (s[i] <= '5')
        s[i] = '3';
    else if (s[i] <= '7')
        s[i] = '5';
    else
        s[i] = '7';
 
    return;
}
 
string primeDigits(string s)
{
    for (int i = 0; i < s.length(); i++) {
 
        // find first non prime char
        if (!isPrime(s[i])) {
 
            // find first char greater than 2
            while (s[i] <= '2' && i >= 0)
                i--;
 
            // like 20
            if (i < 0) {
                i = 0;
                decrease(s, i);
            }
 
            // like 7721
            else
                decrease(s, i);
 
            // replace remaining with 7
            for (int j = i + 1; j < s.length(); j++)
                s[j] = '7';           
 
            break;
        }
    }
 
    return s;
}
 
// Driver code
int main()
{
    string s = "45";
    cout << primeDigits(s) << endl;
 
    s = "1000";
    cout << primeDigits(s) << endl;
 
    s = "7721";
    cout << primeDigits(s) << endl;
 
    s = "7221";
    cout << primeDigits(s) << endl;
 
    s = "74545678912345689748593275897894708927680";
    cout << primeDigits(s) << endl;
 
    return 0;
}

Java

// Java program to find largest number smaller than
// equal to n with all prime digits.
class GFG
{
 
    // check if character is prime
    public static boolean isPrime(char c)
    {
        return (c == '2' || c == '3' || c == '5' || c == '7');
    }
 
    // replace with previous prime character
    public static void decrease(StringBuilder s, int i)
    {
        if (s.charAt(i) <= '2')
        {
 
            // if 2 erase s[i] and replace next with 7
            s.deleteCharAt(i);
            s.setCharAt(i, '7');
        }
        else if (s.charAt(i) == '3')
            s.setCharAt(i, '2');
        else if (s.charAt(i) <= '5')
            s.setCharAt(i, '3');
        else if (s.charAt(i) <= '7')
            s.setCharAt(i, '5');
        else
            s.setCharAt(i, '7');
 
        return;
    }
 
    public static String primeDigits(StringBuilder s)
    {
        for (int i = 0; i < s.length(); i++)
        {
 
            // find first non prime char
            if (!isPrime(s.charAt(i)))
            {
 
                // find first char greater than 2
                while (i >= 0 && s.charAt(i) <= '2')
                    i--;
                 
                // like 20
                if (i < 0)
                {
                    i = 0;
                    decrease(s, i);
                }
                 
                // like 7721
                else
                    decrease(s, i);
 
                // replace remaining with 7
                for (int j = i + 1; j < s.length(); j++)
                    s.setCharAt(j, '7');
                break;
            }
        }
 
        return s.toString();
    }
 
    // Driver code
    public static void main(String[] args)
    {
        StringBuilder s = new StringBuilder("45");
        System.out.println(primeDigits(s));
 
        s = new StringBuilder("1000");
        System.out.println(primeDigits(s));
 
        s = new StringBuilder("7721");
        System.out.println(primeDigits(s));
 
        s = new StringBuilder("7221");
        System.out.println(primeDigits(s));
 
        s = new StringBuilder("74545678912345689748593275897894708927680");
        System.out.println(primeDigits(s));
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python3 program to find largest number
# smaller than equal to n with all prime digits.
 
# check if character is prime
def isPrime(c):
    return (c == '2' or c == '3' or
            c == '5' or c == '7')
 
# replace with previous prime character
def decrease(s, i):
     
    # if 2 erase s[i] and replace next with 7
    if (s[i] <= '2'):
        s.pop(i)
        s[i] = '7'
    elif (s[i] == '3'):
        s[i] = '2'
    elif (s[i] <= '5'):
        s[i] = '3'
    elif (s[i] <= '7'):
        s[i] = '5'
    else:
        s[i] = '7'
 
def primeDigits(s):
    s = [i for i in s]
    i = 0
 
    while i < len(s):
 
        # find first non prime char
        if (isPrime(s[i]) == False):
 
            # find first char greater than 2
            while (s[i] <= '2' and i >= 0):
                i -= 1
 
            # like 20
            if (i < 0):
                i = 0
                decrease(s, i)
         
            # like 7721
            else:
                decrease(s, i)
 
            # replace remaining with 7
            for j in range(i + 1,len(s)):
                s[j] = '7'
 
            break
        i += 1
 
    return "".join(s)
 
# Driver code
s = "45"
print(primeDigits(s))
 
s = "1000"
print(primeDigits(s))
 
s = "7721"
print(primeDigits(s))
 
s = "7221"
print(primeDigits(s))
 
s = "74545678912345689748593275897894708927680"
print(primeDigits(s))
 
# This code is contributed by Mohit Kumar

C#

// C# program to find largest number
// smaller than equal to n with all prime digits.
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
class HelloWorld {
 
    // check if character is prime
    static bool isPrime(char c)
    {
        return (c == '2' || c == '3' || c == '5'
                || c == '7');
    }
 
    // replace with previous prime character
    static char[] decrease(char[] s, int i)
    {
        // if 2 erase s[i] and replace next with 7
        if (s[i] <= '2') {
            s = s.Where((source, index) => index != i).ToArray();
            s[i] = '7';
        }
        else if (s[i] == '3') {
            s[i] = '2';
        }
        else if (s[i] <= '5') {
            s[i] = '3';
        }
        else if (s[i] <= '7') {
            s[i] = '5';
        }
        else {
            s[i] = '7';
        }
        return s;
    }
 
    static string primeDigits(char[] s)
    {
        for (int i = 0; i < s.Length; i++) {
 
            // find first non prime char
            if (isPrime(s[i]) == false) {
                // find first char greater than 2
                while (i >= 0 && s[i] <= '2') {
                    i = i - 1;
                }
 
                // like 20
                if (i < 0) {
                    i = 0;
                    s = decrease(s, i);
                }
 
                // like 7721
                else {
                    s = decrease(s, i);
                }
 
                // replace remaining with 7
                for (int j = i + 1; j < s.Length; j++) {
                    s[j] = '7';
                }
 
                break;
            }
        }
 
        return new string(s);
    }
 
    // Driver code
    static void Main()
    {
 
        char[] s = { '4', '5' };
        Console.WriteLine(primeDigits(s));
 
        char[] s1 = { '1', '0', '0', '0' };
        Console.WriteLine(primeDigits(s1));
 
        char[] s2 = { '7', '7', '2', '1' };
        Console.WriteLine(primeDigits(s2));
 
        char[] s3 = { '7', '2', '2', '1' };
        Console.WriteLine(primeDigits(s3));
 
        char[] s4
            = { '7', '4', '5', '4', '6', '7', '8', '9',
                '1', '2', '3', '4', '5', '6', '8', '9',
                '7', '4', '8', '5', '9', '3', '2', '7',
                '5', '8', '9', '7', '8', '9', '4', '7',
                '0', '8', '9', '2', '7', '6', '8', '0' };
        Console.WriteLine(primeDigits(s4));
    }
}
 
// The code is contributed by Nidhi goel

PHP

<?php
// PHP program to find largest
// number smaller than equal
// to n with all prime digits.
 
// check if character is prime
function isPrime($c)
{
    return ($c == '2' || $c == '3' ||
            $c == '5' || $c == '7') ?
                                  1 : 0;
}
 
// replace with previous
// prime character
function decrease($s, $i)
{
    // if 2 erase s[i] and
    // replace next with 7
    if ($s[$i] <= '2')
    {
         
        $s[$i] = '*';
        $a = str_split($s);
        $s = "";
        for($h = 0; $h < count($a); $h++)
            if($a[$h] != '*')
                $s = $s.$a[$h];
         
        $s[$i] = '7';
    }
 
    else if ($s[$i] == '3')
        $s[$i] = '2';
    else if ($s[$i] <= '5')
        $s[$i] = '3';
    else if ($s[$i] <= '7')
        $s[$i] = '5';
    else
        $s[$i] = '7';
 
    return $s;
}
 
function primeDigits($s)
{
    for ($i = 0; $i < strlen($s); $i++)
    {
 
        // find first non prime char
        if (isPrime($s[$i]) == 0)
        {
 
            // find first char
            // greater than 2
            while ($i >= 0 &&
                   $s[$i] <= '2')
                --$i;
 
            // like 20
            if ($i < 0)
            {
                $i = 0;
                $s = decrease($s, $i);
            }
 
            // like 7721
            else
                $s = decrease($s, $i);
 
            // replace remaining with 7
            for ($j = $i + 1;
                 $j < strlen($s); $j++)
                $s[$j] = '7';    
 
            break;
        }
    }
 
    return $s;
}
 
// Driver code
$s = "45";
echo primeDigits($s) . "\n";
 
$s = "1000";
echo primeDigits($s) . "\n";
 
$s = "7721";
echo primeDigits($s) . "\n";
 
$s = "7221";
echo primeDigits($s) . "\n";
 
$s = "74545678912345689748593275897894708927680";
echo primeDigits($s);
 
// This code is contributed by mits.
?>

Javascript

<script>
// Javascript program to find largest number smaller than
// equal to n with all prime digits.
     
    // check if character is prime
    function isPrime(c)
    {
        return (c == '2' || c == '3' || c == '5' || c == '7');
    }
     
    // replace with previous prime character
    function decrease(s,i)
    {
         
        
        if (s[i] <= '2')
        {
  
            // if 2 erase s[i] and replace next with 7
            s.splice(i,1)
            s[i]= '7';
        }
        else if (s[i] == '3')
            s[i] = '2';
        else if (s[i] <= '5')
            s[i]= '3';
        else if (s[i] <= '7')
            s[i] = '5';
        else
            s[i] = '7';
      
         
        return s;
         
    }
     
    function primeDigits(s)
    {
        for (let i = 0; i < s.length; i++)
        {
  
            // find first non prime char
            if (!isPrime(s[i]))
            {
  
                // find first char greater than 2
                while (i >= 0 && s[i].charCodeAt(0) <= '2'.charCodeAt(0))
                    i--;
                  
                // like 20
                if (i < 0)
                {
                    i = 0;
                    s=decrease(s.split(""), i);
                }
                  
                // like 7721
                else
                    s=decrease(s.split(""), i);
  
                // replace remaining with 7
                for (let j = i + 1; j < s.length; j++)
                    s[j] = '7';
                break;
            }
        }
  
        return s.join("");
    }
     
    // Driver code
    let s = "45";
    document.write(primeDigits(s)+"<br>");
  
    s = "1000";
    document.write(primeDigits(s)+"<br>");
  
    s = "7721";
    document.write(primeDigits(s)+"<br>");
  
    s = "7221";
    document.write(primeDigits(s)+"<br>");
  
    s = "74545678912345689748593275897894708927680";
    document.write(primeDigits(s)+"<br>");
     
     
     
 
// This code is contributed by unknown2108
</script>

Producción: 

37
777
7577
5777
73777777777777777777777777777777777777777

La complejidad temporal del programa anterior es O(N) donde N es la longitud de la string.

Publicación traducida automáticamente

Artículo escrito por rsatish1110 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *