Dado un número N, la tarea es encontrar el número más grande menor o igual que el número dado N tal que al reordenar sus dígitos pueda convertirse en primo.
Ejemplos:
Input : N = 99 Output : 98 Explanation : We can rearrange the digits of 98 to 89 and 89 is a prime number. Input : N = 84896 Output : 84896 Explanation : We can rearrange the digits of 84896 to 46889 which is a prime number.
A continuación se muestra el algoritmo para encontrar un número tan grande num <= N tal que los dígitos de num se pueden reorganizar para obtener un número primo:
Paso de preprocesamiento : Generar una lista de todos los números primos menores o iguales al número dado N. Esto puede hacerse eficientemente utilizando el tamiz de Eratóstenes .
Pasos principales : la idea principal es verificar todos los números de N a 1, si alguno de los números se puede volver a barajar para formar un número primo. El primer número de este tipo que se encuentre será la respuesta.
Para hacer esto, ejecute un ciclo de N a 1 y para cada número:
- Extraiga los dígitos del número dado y guárdelo en un vector.
- Ordena este vector para obtener el número más pequeño que se puede formar usando estos dígitos.
- Para cada permutación de este vector, formaríamos un número y comprobaríamos si el número formado es primo o no. Aquí hacemos uso del paso de preprocesamiento.
- Si es primo, detenemos el ciclo y esta es nuestra respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find a number less than
// or equal to N such that rearranging
// the digits gets a prime number
#include <bits/stdc++.h>
using namespace std;
// Preprocessed vector to store primes
vector<bool> prime(1000001, true);
// Function to generate primes using
// sieve of eratosthenese
void sieve()
{
// Applying sieve of Eratosthenes
prime[0] = prime[1] = false;
for (long long i = 2; i * i <= 1000000; i++) {
if (prime[i]) {
for (long long j = i * i; j <= 1000000; j += i)
prime[j] = false;
}
}
}
// Function to find a number less than
// or equal to N such that rearranging
// the digits gets a prime number
int findNumber(int n)
{
vector<int> v;
bool flag = false;
int num;
// Run loop from n to 1
for (num = n; num >= 1; num--) {
int x = num;
// Clearing the vector
v.clear();
// Extracting the digits
while (x != 0) {
v.push_back(x % 10);
x /= 10;
}
// Sorting the vector to make smallest
// number using digits
sort(v.begin(), v.end());
// Check all permutation of current number
// for primality
while (1) {
long long w = 0;
// Traverse vector to for number
for (auto u : v)
w = w * 10 + u;
// If prime exists
if (prime[w]) {
flag = true;
break;
}
if (flag)
break;
// generating next permutation of vector
if (!next_permutation(v.begin(), v.end()))
break;
}
if (flag)
break;
}
// Required number
return num;
}
// Driver Code
int main()
{
sieve();
int n = 99;
cout << findNumber(n) << endl;
n = 84896;
cout << findNumber(n) << endl;
return 0;
}
Java
// Java Program to find a number less than
// or equal to N such that rearranging
// the digits gets a prime number
import java.util.*;
class GFG{
// Preprocessed vector to store primes
static boolean[] prime = new boolean[1000001];
static boolean next_permutation(Vector<Integer> v) {
int p[] = new int[v.size()];
for(int l = 0; l< p.length;l++) {
p[l] = v.elementAt(l);
}
for (int a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.length - 1;; --b)
if (p[b] > p[a]) {
int t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Function to generate primes using
// sieve of eratosthenese
static void sieve()
{
Arrays.fill(prime, true);
// Applying sieve of Eratosthenes
prime[0] = prime[1] = false;
for (int i = 2; i * i <= 1000000; i++) {
if (prime[i]==true) {
for (int j = i * i; j <= 1000000; j += i)
prime[j] = false;
}
}
}
// Function to find a number less than
// or equal to N such that rearranging
// the digits gets a prime number
static int findNumber(int n)
{
Vector<Integer> v = new Vector<>();
boolean flag = false;
int num;
// Run loop from n to 1
for (num = n; num >= 1; num--) {
int x = num;
// Clearing the vector
v.clear();
// Extracting the digits
while (x != 0) {
v.add(x % 10);
x /= 10;
}
// Sorting the vector to make smallest
// number using digits
Collections.sort(v);
// Check all permutation of current number
// for primality
while (true) {
int w = 0;
// Traverse vector to for number
for (int u : v)
w = w * 10 + u;
// If prime exists
if (prime[w]==true) {
flag = true;
break;
}
if (flag)
break;
// generating next permutation of vector
if (!next_permutation(v))
break;
}
if (flag)
break;
}
// Required number
return num;
}
// Driver Code
public static void main(String[] args)
{
sieve();
int n = 99;
System.out.print(findNumber(n) +"\n");
n = 84896;
System.out.print(findNumber(n) +"\n");
}
}
// This code contributed by umadevi9616
Python3
# Python 3 Program to find a number less than # or equal to N such that rearranging # the digits gets a prime number from math import sqrt def next_permutation(a): # Generate the lexicographically # next permutation inplace. # https://en.wikipedia.org/wiki/Permutation # Generation_in_lexicographic_order # Return false if there is no next permutation. # Find the largest index i such that # a[i] < a[i + 1]. If no such index exists, # the permutation is the last permutation for i in reversed(range(len(a) - 1)): if a[i] < a[i + 1]: break # found else: # no break: not found return False # no next permutation # Find the largest index j greater than i # such that a[i] < a[j] j = next(j for j in reversed(range(i + 1, len(a))) if a[i] < a[j]) # Swap the value of a[i] with that of a[j] a[i], a[j] = a[j], a[i] # Reverse sequence from a[i + 1] up to and # including the final element a[n] a[i + 1:] = reversed(a[i + 1:]) return True # Preprocessed vector to store primes prime = [True for i in range(1000001)] # Function to generate primes using # sieve of eratosthenese def sieve(): # Applying sieve of Eratosthenes prime[0] = False prime[1] = False for i in range(2,int(sqrt(1000000)) + 1, 1): if (prime[i]): for j in range(i * i, 1000001, i): prime[j] = False # Function to find a number less than # or equal to N such that rearranging # the digits gets a prime number def findNumber(n): v = [] flag = False # Run loop from n to 1 num = n while(num >= 1): x = num v.clear() # Extracting the digits while (x != 0): v.append(x % 10) x = int(x / 10) # Sorting the vector to make smallest # number using digits v.sort(reverse = False) # Check all permutation of current number # for primality while (1): w = 0 # Traverse vector to for number for u in v: w = w * 10 + u # If prime exists if (prime[w]): flag = True break if (flag): break # generating next permutation of vector if (next_permutation(v) == False): break if (flag): break num -= 1 # Required number return num # Driver Code if __name__ == '__main__': sieve() n = 99 print(findNumber(n)) n = 84896 print(findNumber(n)) # This code is contributed by # Surendra_Gangwar
C#
// C# Program to find a number less than
// or equal to N such that rearranging
// the digits gets a prime number
using System;
using System.Collections.Generic;
public class GFG {
// Preprocessed vector to store primes
static bool[] prime = new bool[1000001];
static bool next_permutation(List<int> v) {
int []p = new int[v.Count];
for (int l = 0; l < p.Length; l++) {
p[l] = v[l];
}
for (int a = p.Length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.Length - 1;; --b)
if (p[b] > p[a]) {
int t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.Length - 1; a < b; ++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Function to generate primes using
// sieve of eratosthenese
static void sieve() {
for (int j = 0; j < prime.GetLength(0); j++)
prime[j] = true;
// Applying sieve of Eratosthenes
prime[0] = prime[1] = false;
for (int i = 2; i * i <= 1000000; i++) {
if (prime[i] == true) {
for (int j = i * i; j <= 1000000; j += i)
prime[j] = false;
}
}
}
// Function to find a number less than
// or equal to N such that rearranging
// the digits gets a prime number
static int findNumber(int n) {
List<int> v = new List<int>();
bool flag = false;
int num;
// Run loop from n to 1
for (num = n; num >= 1; num--) {
int x = num;
// Clearing the vector
v.Clear();
// Extracting the digits
while (x != 0) {
v.Add(x % 10);
x /= 10;
}
// Sorting the vector to make smallest
// number using digits
v.Sort();
// Check all permutation of current number
// for primality
while (true) {
int w = 0;
// Traverse vector to for number
foreach (int u in v)
w = w * 10 + u;
// If prime exists
if (prime[w] == true) {
flag = true;
break;
}
if (flag)
break;
// generating next permutation of vector
if (!next_permutation(v))
break;
}
if (flag)
break;
}
// Required number
return num;
}
// Driver Code
public static void Main(String[] args) {
sieve();
int n = 99;
Console.Write(findNumber(n) + "\n");
n = 84896;
Console.Write(findNumber(n) + "\n");
}
}
// This code is contributed by umadevi9616 -
Javascript
<script>
// javascript Program to find a number less than
// or equal to N such that rearranging
// the digits gets a prime number
// Preprocessed vector to store primes
var prime = Array(1000001).fill(true);
function next_permutation(v)
{
var p = Array(v.length).fill(0);
for (l = 0; l < p.length; l++) {
p[l] = v[l];
}
for (a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (b = p.length - 1;; --b)
if (p[b] > p[a]) {
var t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Function to generate primes using
// sieve of eratosthenese
function sieve() {
// Applying sieve of Eratosthenes
prime[0] = prime[1] = false;
for (i = 2; i * i <= 1000000; i++) {
if (prime[i] == true) {
for (j = i * i; j <= 1000000; j += i)
prime[j] = false;
}
}
}
// Function to find a number less than
// or equal to N such that rearranging
// the digits gets a prime number
function findNumber(n) {
var v = new Array();
var flag = false;
var num;
// Run loop from n to 1
for (num = n; num >= 1; num--) {
var x = num;
// Clearing the vector
v = new Array();
// Extracting the digits
while (x != 0) {
v.push(x % 10);
x = parseInt(x/10);
}
// Sorting the vector to make smallest
// number using digits
v.sort();
// Check all permutation of current number
// for primality
while (true) {
var w = 0;
// Traverse vector to for number
v.forEach(function (item) {
w = w * 10 + item;
});
// If prime exists
if (prime[w] == true) {
flag = true;
break;
}
if (flag)
break;
// generating next permutation of vector
if (!next_permutation(v))
break;
}
if (flag)
break;
}
// Required number
return num;
}
// Driver Code
sieve();
var n = 99;
document.write(findNumber(n) + "<br/>");
n = 84896;
document.write(findNumber(n) + "<br/>");
// This code is contributed by umadevi9616
</script>
Producción:
98 84896
Complejidad de tiempo: O(MAX*sqrt(MAX)), donde MAX es 1000000.
Espacio auxiliar: O(MAX), donde MAX es 1000000.
Publicación traducida automáticamente
Artículo escrito por sharadgoyal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA