Encuentre un número primo S que contenga el número N dado en él

Dado un número entero N , encuentre un número primo S tal que todos los dígitos de N estén en una secuencia contigua. Puede haber varias respuestas. Imprime cualquiera de ellos.

Ejemplo:

Entrada: N = 42
Salida: 42013
Explicación: 42 013 es un número primo y 42 aparece como un número contiguo en él. 15 42 7 también es una respuesta correcta.

Entrada: N = 47
Salida: 47
Explicación: 47 en sí mismo es un número primo

Enfoque ingenuo: se pueden seguir los siguientes pasos:

• Iterar a través de todos los números a partir de N
• Convierta cada número en una string con la función to_string()
• Verifique la substring requerida usando la función str.find()
• Si hay algún número que tiene N como substring y es primo, devuelve ese número

Complejidad temporal: O(S), donde S es el número primo requerido

Enfoque eficiente: se pueden seguir los siguientes pasos:

• Se puede utilizar el hecho de que un número con valor hasta 1e12, entre dos primos consecutivos, hay como máximo 464 números no primos.
• Extiende el número actual N multiplicándolo por 1000.
• Después de eso, repita los siguientes números uno por uno y verifique cada uno de ellos.
• Si el número es primo, imprima ese número.
• Es fácil ver que la primera condición siempre seguirá como los dígitos, excepto que los últimos tres serán N.

A continuación se muestra la implementación del enfoque anterior:

// C++ Implementation for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a number is prime
bool isPrime(long long N)
{
    if (N == 1)
        return false;
    for (long long i = 2; i <= sqrt(N); i++)
 
        // If N is divisible then its not a prime
        if (N % i == 0)
            return false;
    return true;
}
// Function to print a prime number
// which has N as a substring
long long prime_substring_Number(long long N)
{
    // Check for the base case
    if (N == 0) {
        return 103;
 
        // 103 is a prime
    }
 
    // multiply N by 10^3
    // Check for numbers from
    // N*1000 to N*1000 + 464
    N *= 1000;
    for (long long i = N; i < N + 465; i++) {
        if (isPrime(i)) {
            return i;
        }
    }
    return 0;
}
 
// Driver Code
int main()
{
    long N = 42;
    cout << prime_substring_Number(N);
}

/*package whatever //do not write package name here */
import java.io.*;
class GFG {
static boolean isPrime(long N)
{
    if (N == 1)
        return false;
    for (long i = 2; i <= Math.sqrt(N); i++)
 
        // If N is divisible then its not a prime
        if (N % i == 0)
            return false;
    return true;
}
   
// Function to print a prime number
// which has N as a substring
static long prime_substring_Number(long N)
{
    // Check for the base case
    if (N == 0) {
        return 103;
 
        // 103 is a prime
    }
 
    // multiply N by 10^3
    // Check for numbers from
    // N*1000 to N*1000 + 464
    N *= 1000;
    for (long i = N; i < N + 465; i++) {
        if (isPrime(i)) {
            return i;
        }
    }
    return 0;
}
 
// Driver Code
    public static void main(String[] args)
    {
        long N = 42;
        System.out.println(prime_substring_Number(N));
    }
}
 
// This code is contributed by maddler.

# python Implementation for the above approach
# importing math library
from math import *
 
# Function to check if a number is prime
def isPrime(N) :
    if N > 1:
       
      # Iterate from 2 to n / 2
      for i in range(2, int(N/2)+1):
         
        # If num is divisible by any number between
        # 2 and n / 2, it is not prime
        if (N % i) == 0:
            return False
      else:
        return True 
    else:
        return False
       
# Function to print a prime number
# which has N as a substring
def prime_substring_Number(N) :
   
    # Check for the base case
    if (N == 0) :
        return 103
 
        # 103 is a prime
 
    # multiply N by 10^3
    # Check for numbers from
    # N*1000 to N*1000 + 464
    N =N * 1000
    for i in range(N,N + 465):
        if (isPrime(i)) :
            return i
         
    return 0
 
# Driver Code
N = 42
print(prime_substring_Number(N))
 
# This code is contributed by anudeep23042002.

// C# Implementation for the above approach
using System;
class GFG {
 
    // Function to check if a number is prime
    static bool isPrime(long N)
    {
        if (N == 1)
            return false;
        for (long i = 2; i <= Math.Sqrt(N); i++)
 
            // If N is divisible then its not a prime
            if (N % i == 0)
                return false;
        return true;
    }
    // Function to print a prime number
    // which has N as a substring
    static long prime_substring_Number(long N)
    {
        // Check for the base case
        if (N == 0) {
            return 103;
 
            // 103 is a prime
        }
 
        // multiply N by 10^3
        // Check for numbers from
        // N*1000 to N*1000 + 464
        N *= 1000;
        for (long i = N; i < N + 465; i++) {
            if (isPrime(i)) {
                return i;
            }
        }
        return 0;
    }
 
    // Driver Code
    public static void Main()
    {
        long N = 42;
        Console.WriteLine(prime_substring_Number(N));
    }
}
 
// This code is contributed y ukasp.

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to check if a number is prime
        function isPrime(N) {
            if (N == 1)
                return false;
            for (let i = 2; i <= Math.sqrt(N); i++)
 
                // If N is divisible then its not a prime
                if (N % i == 0)
                    return false;
            return true;
        }
         
        // Function to print a prime number
        // which has N as a substring
        function prime_substring_Number(N)
        {
         
            // Check for the base case
            if (N == 0) {
                return 103;
 
                // 103 is a prime
            }
 
            // multiply N by 10^3
            // Check for numbers from
            // N*1000 to N*1000 + 464
            N *= 1000;
            for (let i = N; i < N + 465; i++) {
                if (isPrime(i)) {
                    return i;
                }
            }
            return 0;
        }
 
        // Driver Code
        let N = 42;
        document.write(prime_substring_Number(N));
 
// This code is contributed by Potta Lokesh
    </script>

42013

Complejidad de tiempo: O(sqrt(N*1000)*300)
Espacio auxiliar: O(1)