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