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