Dado un número ‘n’, necesitamos encontrar el n-ésimo número cuyos dígitos sean números primos, es decir, 2, 3, 5, 7… En otras palabras, debe encontrar el n-ésimo número de esta secuencia. 2, 3, 5, 5, 22, 23……
Dado que el n-ésimo número encontrado será menor que 10^18
Ejemplos:
Input : 10
Output : 33
2, 3, 5, 7, 22, 23, 25,
27, 32, 33
Input : 21
Output : 222
Hay cuatro dígitos primos 2, 3, 5 y 7. La primera observación es que la cantidad de números de longitud x y compuestos de dígitos primos se 
debe a que para cada posición tiene 4 opciones, por lo que el número total es 4^x.
Entonces, el recuento total de tales números cuya longitud es = 1 a len (es decir, 2 o 3 o más) será 4*((4 len – 1)/3). (Esta es la suma de GP con el primer término 4 y la razón común 4)
El algoritmo se divide principalmente en dos pasos.
- Encontramos el número de dígitos en el número n usando la observación anterior. Empezamos desde len = 0 y seguimos incrementándolo mientras su valor sea menor que 4*((4 len – 1)/3).
- Ahora sabemos el número de dígitos en el n-ésimo número. También conocemos el conteo de números con (len-1) dígitos. Deje que este recuento sea ‘prev_count’. Ahora uno por uno encontramos dígitos en nuestro resultado. Primero fije 2 en el i-ésimo lugar (suponiendo que todos los lugares hasta i-1 ya estén llenos), tenemos 4^(len – i) números posibles y para verificar si 2 es el candidato correcto o no, verifique si cuenta los números después poner 2 es mayor o igual que n o no. Si es cierto, entonces 2 es el candidato correcto; si esto no es cierto, significa que si fijamos 2 en el i-ésimo lugar, solo se pueden cubrir los números prev_count + 4^(len-i). Así que aumente prev_count en 4^(len-i) y repita este paso para 3, verifique si 3 encaja en el iésimo lugar o no. Si no, elija 5. Si 5 tampoco encaja, elija 7. Está garantizado que 7 lo hará ajustarlo si 2, 3 y 5 no encajan, porque estamos seguros de que la longitud del n-ésimo número es solo len.
A continuación se muestra la implementación de los pasos anteriores.
C++
// C++ implementation for finding nth number
// made of prime digits only
#include <bits/stdc++.h>
using namespace std;
// Prints n-th number where each digit is a
// prime number
void nthprimedigitsnumber(long long n)
{
// Finding the length of n-th number
long long len = 1;
// Count of numbers with len-1 digits
long long prev_count = 0;
while (true) {
// Count of numbers with i digits
long long curr_count = prev_count + pow(4, len);
// if i is the length of such number
// then n<4*(4^(i-1)-1)/3 and n>= 4*(4 ^ i-1)/3
// if a valid i is found break the loop
if (prev_count < n && curr_count >= n)
break;
// check for i + 1
len++;
prev_count = curr_count;
}
// Till now we have covered 'prev_count' numbers
// Finding ith digit at ith place
for (int i = 1; i <= len; i++) {
// j = 1 means 2 j = 2 means ...j = 4 means 7
for (long long j = 1; j <= 4; j++) {
// if prev_count + 4 ^ (len-i) is less
// than n, increase prev_count by 4^(x-i)
if (prev_count + pow(4, len - i) < n)
prev_count += pow(4, len - i);
// else print the ith digit and break
else {
if (j == 1)
cout << "2";
else if (j == 2)
cout << "3";
else if (j == 3)
cout << "5";
else if (j == 4)
cout << "7";
break;
}
}
}
cout << endl;
}
// Driver function
int main()
{
nthprimedigitsnumber(10);
nthprimedigitsnumber(21);
return 0;
}
Java
// Java implementation for finding nth number
// made of prime digits only
import static java.lang.Math.pow;
class Test {
// Prints n-th number where each digit is a
// prime number
static void nthprimedigitsnumber(long n)
{
// Finding the length of n-th number
long len = 1;
// Count of numbers with len-1 digits
long prev_count = 0;
while (true) {
// Count of numbers with i digits
long curr_count = (long)(prev_count + pow(4, len));
// if i is the length of such number
// then n<4*(4^(i-1)-1)/3 and n>= 4*(4 ^ i-1)/3
// if a valid i is found break the loop
if (prev_count < n && curr_count >= n)
break;
// check for i + 1
len++;
prev_count = curr_count;
}
// Till now we have covered 'prev_count' numbers
// Finding ith digit at ith place
for (int i = 1; i <= len; i++) {
// j = 1 means 2 j = 2 means ...j = 4 means 7
for (long j = 1; j <= 4; j++) {
// if prev_count + 4 ^ (len-i) is less
// than n, increase prev_count by 4^(x-i)
if (prev_count + pow(4, len - i) < n)
prev_count += pow(4, len - i);
// else print the ith digit and break
else {
if (j == 1)
System.out.print("2");
else if (j == 2)
System.out.print("3");
else if (j == 3)
System.out.print("5");
else if (j == 4)
System.out.print("7");
break;
}
}
}
System.out.println();
}
// Driver method
public static void main(String args[])
{
nthprimedigitsnumber(10);
nthprimedigitsnumber(21);
}
}
Python3
# Python3 implementation for
# finding nth number made of
# prime digits only
import math
# Prints n-th number where
# each digit is a prime number
def nthprimedigitsnumber(n):
# Finding the length
# of n-th number
len = 1;
# Count of numbers
# with len-1 digits
prev_count = 0;
while(1):
# Count of numbers
# with i digits
curr_count = (prev_count +
math.pow(4, len));
# if i is the length of such
# number then n<4*(4^(i-1)-1)/3
# and n>= 4*(4 ^ i-1)/3 if a valid
# i is found break the loop
if (prev_count < n and
curr_count >= n):
break;
# check for i + 1
len += 1;
prev_count = curr_count;
# Till now we have covered
# 'prev_count' numbers
# Finding ith digit at ith place
for i in range (1, len + 1):
# j = 1 means 2 j = 2
# means ...j = 4 means 7
for j in range(1, 5):
# if prev_count + 4 ^ (len-i)
# is less than n, increase
# prev_count by 4^(x-i)
if (prev_count + pow(4, len - i) < n):
prev_count += pow(4, len - i);
# else print the ith
# digit and break
else:
if (j == 1):
print("2", end = "");
else if (j == 2):
print("3", end = "");
else if (j == 3):
print("5", end = "");
else if (j == 4):
print("7", end = "");
break;
print();
# Driver Code
nthprimedigitsnumber(10);
nthprimedigitsnumber(21);
# This code is contributed by mits
C#
// C# implementation for finding nth
// number made of prime digits only
using System;
public class GFG {
// Prints n-th number where each
// digit is a prime number
static void nthprimedigitsnumber(long n)
{
// Finding the length of n-th number
long len = 1;
// Count of numbers with len-1 digits
long prev_count = 0;
while (true) {
// Count of numbers with i digits
long curr_count = (long)(prev_count +
Math.Pow(4, len));
// if i is the length of such number
// then n<4*(4^(i-1)-1)/3 and n>= 4*(4 ^ i-1)/3
// if a valid i is found break the loop
if (prev_count < n && curr_count >= n)
break;
// check for i + 1
len++;
prev_count = curr_count;
}
// Till now we have covered 'prev_count' numbers
// Finding ith digit at ith place
for (int i = 1; i <= len; i++) {
// j = 1 means 2 j = 2 means ...j = 4 means 7
for (long j = 1; j <= 4; j++) {
// if prev_count + 4 ^ (len-i) is less
// than n, increase prev_count by 4^(x-i)
if (prev_count + Math.Pow(4, len - i) < n)
prev_count += (long)Math.Pow(4, len - i);
// else print the ith digit and break
else {
if (j == 1)
Console.Write("2");
else if (j == 2)
Console.Write("3");
else if (j == 3)
Console.Write("5");
else if (j == 4)
Console.Write("7");
break;
}
}
}
Console.WriteLine();
}
// Driver method
public static void Main()
{
nthprimedigitsnumber(10);
nthprimedigitsnumber(21);
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP implementation for finding
// nth number made of prime digits only
// Prints n-th number where
// each digit is a prime number
function nthprimedigitsnumber($n)
{
// Finding the length
// of n-th number
$len = 1;
// Count of numbers
// with len-1 digits
$prev_count = 0;
while (true)
{
// Count of numbers
// with i digits
$curr_count = $prev_count +
pow(4, $len);
// if i is the length of such
// number then n<4*(4^(i-1)-1)/3
// and n>= 4*(4 ^ i-1)/3 if a valid
// i is found break the loop
if ($prev_count < $n &&
$curr_count >= $n)
break;
// check for i + 1
$len++;
$prev_count = $curr_count;
}
// Till now we have covered
// 'prev_count' numbers
// Finding ith digit at ith place
for ($i = 1; $i <= $len; $i++)
{
// j = 1 means 2 j = 2
// means ...j = 4 means 7
for ($j = 1; $j <= 4; $j++)
{
// if prev_count + 4 ^ (len-i)
// is less than n, increase
// prev_count by 4^(x-i)
if ($prev_count +
pow(4, $len - $i) < $n)
$prev_count += pow(4, $len - $i);
// else print the ith
// digit and break
else
{
if ($j == 1)
echo "2";
else if ($j == 2)
echo "3";
else if ($j == 3)
echo "5";
else if ($j == 4)
echo "7";
break;
}
}
}
echo "\n";
}
// Driver Code
nthprimedigitsnumber(10);
nthprimedigitsnumber(21);
// This code is contributed by ajit
?>
Javascript
<script>
// javascript implementation for finding nth number
// made of prime digits only
// Prints n-th number where each digit is a
// prime number
function nthprimedigitsnumber(n)
{
// Finding the length of n-th number
var len = 1;
// Count of numbers with len-1 digits
var prev_count = 0;
while (true) {
// Count of numbers with i digits
var curr_count = (prev_count + Math.pow(4, len));
// if i is the length of such number
// then n<4*(4^(i-1)-1)/3 and n>= 4*(4 ^ i-1)/3
// if a valid i is found break the loop
if (prev_count < n && curr_count >= n)
break;
// check for i + 1
len++;
prev_count = curr_count;
}
// Till now we have covered 'prev_count' numbers
// Finding ith digit at ith place
for (var i = 1; i <= len; i++) {
// j = 1 means 2 j = 2 means ...j = 4 means 7
for (var j = 1; j <= 4; j++) {
// if prev_count + 4 ^ (len-i) is less
// than n, increase prev_count by 4^(x-i)
if (prev_count + Math.pow(4, len - i) < n)
prev_count += Math.pow(4, len - i);
// else print the ith digit and break
else {
if (j == 1)
document.write("2");
else if (j == 2)
document.write("3");
else if (j == 3)
document.write("5");
else if (j == 4)
document.write("7");
break;
}
}
}
document.write('<br>');
}
// Driver method
nthprimedigitsnumber(10);
nthprimedigitsnumber(21);
// This code is contributed by Amit Katiyar
</script>
Producción
33 222
Solución alternativa (Funciona en O(Log n)
In this post, a O(log n) solution is discussed
which is based on below pattern in numbers. The
numbers can be seen
""
/ | | \
2 3 5 7
/ | | \ / | | \ / | | \ / | | \
22 23 25 27 32 33 35 37 52 53 55 57 72 73 75 77
/||\/||\/||\/||\ /||\/||\/||\/||\ /||\/||\/||\/||\ /||\/||\/||\/||\
We can notice following :
1st. 5th, 9th. 13th, ..... numbers have 2 as last digit.
2nd. 6th, 10th. 14th, ..... numbers have 3 as last digit.
3nd. 7th, 11th. 15th, ..... numbers have 5 as last digit.
4th. 8th, 12th. 16th, ..... numbers have 7 as last digit.
Implementación:
C++
// CPP program to find n-th number with
// prime digits 2, 3 and 7
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
string nthprimedigitsnumber(int number)
{
int rem;
string num;
while (number) {
// remainder for check element position
rem = number % 4;
switch (rem) {
// if number is 1st position in tree
case 1:
num.push_back('2');
break;
// if number is 2nd position in tree
case 2:
num.push_back('3');
break;
// if number is 3rd position in tree
case 3:
num.push_back('5');
break;
// if number is 4th position in tree
case 0:
num.push_back('7');
break;
}
if (number % 4 == 0)
number--;
number = number / 4;
}
reverse(num.begin(), num.end());
return num;
}
// Driver code
int main()
{
int number = 21;
cout << nthprimedigitsnumber(10) << "\n";
cout << nthprimedigitsnumber(21) << "\n";
return 0;
}
Java
// Java program to find n-th number with
// prime digits 2, 3 and 7
import java.util.*;
class GFG{
static String nthprimedigitsnumber(int number)
{
int rem;
String num="";
while (number>0) {
// remainder for check element position
rem = number % 4;
switch (rem) {
// if number is 1st position in tree
case 1:
num+='2';
break;
// if number is 2nd position in tree
case 2:
num+='3';
break;
// if number is 3rd position in tree
case 3:
num+='5';
break;
// if number is 4th position in tree
case 0:
num+='7';
break;
}
if (number % 4 == 0)
number--;
number = number / 4;
}
return new StringBuilder(num).reverse().toString();
}
// Driver code
public static void main(String[] args)
{
int number = 21;
System.out.println(nthprimedigitsnumber(10));
System.out.println(nthprimedigitsnumber(21));
}
}
// This code is contributed by mits
Python3
# Python3 program to find n-th number # with prime digits 2, 3 and 7 def nthprimedigitsnumber(number): num = ""; while (number > 0): # remainder for check element position rem = number % 4; # if number is 1st position in tree if (rem == 1): num += '2'; # if number is 2nd position in tree if (rem == 2): num += '3'; # if number is 3rd position in tree if (rem == 3): num += '5'; # if number is 4th position in tree if (rem == 0): num += '7'; if (number % 4 == 0): number = number - 1 number = number // 4; return num[::-1]; # Driver code number = 21; print(nthprimedigitsnumber(10)); print(nthprimedigitsnumber(number)); # This code is contributed by mits
C#
// C# program to find n-th number with
// prime digits 2, 3 and 7
using System;
class GFG{
static string nthprimedigitsnumber(int number)
{
int rem;
string num="";
while (number>0) {
// remainder for check element position
rem = number % 4;
switch (rem) {
// if number is 1st position in tree
case 1:
num+='2';
break;
// if number is 2nd position in tree
case 2:
num+='3';
break;
// if number is 3rd position in tree
case 3:
num+='5';
break;
// if number is 4th position in tree
case 0:
num+='7';
break;
}
if (number % 4 == 0)
number--;
number = number / 4;
}
char[] st = num.ToCharArray();
Array.Reverse(st);
return new string(st);
}
// Driver code
static void Main()
{
int number = 21;
Console.WriteLine(nthprimedigitsnumber(10));
Console.WriteLine(nthprimedigitsnumber(number));
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to find n-th number with
// prime digits 2, 3 and 7
function nthprimedigitsnumber($number)
{
$num = "";
while ($number > 0)
{
// remainder for check element position
$rem = $number % 4;
switch ($rem)
{
// if number is 1st position in tree
case 1:
$num .= '2';
break;
// if number is 2nd position in tree
case 2:
$num .= '3';
break;
// if number is 3rd position in tree
case 3:
$num .= '5';
break;
// if number is 4th position in tree
case 0:
$num .= '7';
break;
}
if ($number % 4 == 0)
$number--;
$number = (int)($number / 4);
}
return strrev($num);
}
// Driver code
$number = 21;
print(nthprimedigitsnumber(10) . "\n");
print(nthprimedigitsnumber($number));
// This code is contributed by mits
Javascript
<script>
// Javascript program to find n-th number with prime digits 2, 3 and 7
function nthprimedigitsnumber(number)
{
let rem;
let num="";
while (number>0) {
// remainder for check element position
rem = number % 4;
switch (rem) {
// if number is 1st position in tree
case 1:
num+='2';
break;
// if number is 2nd position in tree
case 2:
num+='3';
break;
// if number is 3rd position in tree
case 3:
num+='5';
break;
// if number is 4th position in tree
case 0:
num+='7';
break;
}
if (number % 4 == 0)
number--;
number = parseInt(number / 4, 10);
}
let st = num.split('');
st.reverse();
return (st.join(""));
}
let number = 21;
document.write(nthprimedigitsnumber(10) + "</br>");
document.write(nthprimedigitsnumber(number));
</script>
Producción
33 222
Este artículo es una contribución de Ayush Jha y Devanshu agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA