El primo especial más pequeño que es mayor o igual a un número dado

Dado un número N. La tarea es encontrar el primo especial más pequeño que sea mayor o igual que N.
Un primo especial es un número que se puede crear colocando dígitos uno tras otro de modo que todos los números resultantes sean primos. 
Ejemplos: 
 

Input: N = 379
Output: 379
379 can be created as => 3 => 37 => 379
Here, all the numbers ie. 3, 37, 379 are prime.

Input:N = 100
Output: 233

Planteamiento: La idea es usar Tamiz de Eratóstenes. Construya la array de tamices hasta el número N*10 (suponiendo que el número exista en ese rango). Luego comience iterativamente desde el número N verificando si el número es primo. Si es primo, compruebe si es primo especial o no.
Ahora, para comprobar si un número es un primo especial o no. Siga dividiendo el número por 10 y en cada punto verifique si el número restante es primo o no, lo cual podemos hacer consultando nuestra array Sieve que hemos construido.
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to find the Smallest Special Prime
// which is greater than or equal to a given number
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether the number
// is a special prime or not
bool checkSpecialPrime(bool* sieve, int num)
{
    // While number is not equal to zero
    while (num) {
        // If the number is not prime
        // return false.
        if (!sieve[num]) {
            return false;
        }
 
        // Else remove the last digit
        // by dividing the number by 10.
        num /= 10;
    }
 
    // If the number has become zero
    // then the number is special prime,
    // hence return true
    return true;
}
 
// Function to find the Smallest Special Prime
// which is greater than or equal to a given number
void findSpecialPrime(int N)
{
    bool sieve[N*10];
 
    // Initially all numbers are considered Primes.
    memset(sieve, true, sizeof(sieve));
    sieve[0] = sieve[1] = false;
    for (long long i = 2; i <= N*10; i++) {
        if (sieve[i]) {
 
            for (long long j = i * i; j <= N*10; j += i) {
                sieve[j] = false;
            }
        }
    }
 
    // There is always an answer possible
    while (true) {
        // Checking if the number is a
        // special prime or not
        if (checkSpecialPrime(sieve, N)) {
            // If yes print the number
            // and break the loop.
            cout << N << '\n';
            break;
        }
        // Else increment the number.
        else
            N++;
    }
}
 
// Driver code
int main()
{
    int N = 379;
 
    findSpecialPrime(N);
 
    N = 100;
    findSpecialPrime(N);
 
    return 0;
}

// Java program to find the Smallest Special Prime
// which is greater than or equal to a given number
 
class GFG
{
     
// Function to check whether the number
// is a special prime or not
static boolean checkSpecialPrime(boolean []sieve, int num)
{
    // While number is not equal to zero
    while (num > 0)
    {
        // If the number is not prime
        // return false.
        if (sieve[num])
        {
            return false;
        }
 
        // Else remove the last digit
        // by dividing the number by 10.
        num /= 10;
    }
 
    // If the number has become zero
    // then the number is special prime,
    // hence return true
    return true;
}
 
// Function to find the Smallest Special Prime
// which is greater than or equal to a given number
static void findSpecialPrime(int N)
{
    boolean[] sieve = new boolean[N * 10 + 1];
 
    // Initially all numbers are considered Primes.
    sieve[0] = sieve[1] = true;
    for (int i = 2; i <= N * 10; i++)
    {
        if (!sieve[i])
        {
            for (int j = i * i; j <= N * 10; j += i)
            {
                sieve[j] = true;
            }
        }
    }
 
    // There is always an answer possible
    while (true)
    {
        // Checking if the number is a
        // special prime or not
        if (checkSpecialPrime(sieve, N))
        {
            // If yes print the number
            // and break the loop.
            System.out.println(N);
            break;
        }
         
        // Else increment the number.
        else
            N++;
    }
}
 
// Driver code
public static void main(String[] args)
{
    int N = 379;
 
    findSpecialPrime(N);
 
    N = 100;
    findSpecialPrime(N);
}
}
 
// This code contributed by Rajput-Ji

# Python 3 program to find the Smallest
# Special Prime which is greater than or
# equal to a given number
 
# Function to check whether the number
# is a special prime or not
def checkSpecialPrime(sieve, num):
     
    # While number is not equal to zero
    while (num):
         
        # If the number is not prime
        # return false.
        if (sieve[num] == False):
            return False
 
        # Else remove the last digit
        # by dividing the number by 10.
        num = int(num / 10)
 
    # If the number has become zero
    # then the number is special prime,
    # hence return true
    return True
 
# Function to find the Smallest Special
# Prime which is greater than or equal
# to a given number
def findSpecialPrime(N):
    sieve = [True for i in range(N * 10 + 1)]
 
    sieve[0] = False
    sieve[1] = False
 
    # sieve for finding the Primes
    for i in range(2, N * 10 + 1):
        if (sieve[i]):
            for j in range(i * i, N * 10 + 1, i):
                sieve[j] = False
     
    # There is always an answer possible
    while (True):
         
        # Checking if the number is a
        # special prime or not
        if (checkSpecialPrime(sieve, N)):
             
            # If yes print the number
            # and break the loop.
            print(N)
            break
     
        # Else increment the number.
        else:
            N += 1
 
# Driver code
if __name__ == '__main__':
    N = 379
 
    findSpecialPrime(N)
 
    N = 100
    findSpecialPrime(N)
 
# This code is contributed by
# Surendra_Gangwar

// C# program to find the Smallest Special Prime
// which is greater than or equal to a given number
using System;
 
class GFG
{
     
// Function to check whether the number
// is a special prime or not
static bool checkSpecialPrime(bool []sieve, int num)
{
    // While number is not equal to zero
    while (num > 0)
    {
        // If the number is not prime
        // return false.
        if (sieve[num])
        {
            return false;
        }
 
        // Else remove the last digit
        // by dividing the number by 10.
        num /= 10;
    }
 
    // If the number has become zero
    // then the number is special prime,
    // hence return true
    return true;
}
 
// Function to find the Smallest Special Prime
// which is greater than or equal to a given number
static void findSpecialPrime(int N)
{
    bool[] sieve = new bool[N * 10 + 1];
 
    // Initially all numbers are considered Primes.
    sieve[0] = sieve[1] = true;
    for (int i = 2; i <= N * 10; i++)
    {
        if (!sieve[i])
        {
            for (int j = i * i; j <= N * 10; j += i)
            {
                sieve[j] = true;
            }
        }
    }
 
    // There is always an answer possible
    while (true)
    {
        // Checking if the number is a
        // special prime or not
        if (checkSpecialPrime(sieve, N))
        {
            // If yes print the number
            // and break the loop.
            Console.WriteLine(N);
            break;
        }
         
        // Else increment the number.
        else
            N++;
    }
}
 
// Driver code
static void Main()
{
    int N = 379;
 
    findSpecialPrime(N);
 
    N = 100;
    findSpecialPrime(N);
}
}
 
// This code is contributed by mits

<?php
// PHP program to find the Smallest Special
// Prime which is greater than or equal
// to a given number
 
// Function to check whether the number
// is a special prime or not
function checkSpecialPrime($sieve, $num)
{
    // While number is not equal to zero
    while ($num)
    {
        // If the number is not prime
        // return false.
        if (!$sieve[$num])
        {
            return false;
        }
 
        // Else remove the last digit
        // by dividing the number by 10.
        $num = floor($num / 10);
    }
 
    // If the number has become zero
    // then the number is special prime,
    // hence return true
    return true;
}
 
// Function to find the Smallest Special 
// Prime which is greater than or equal
// to a given number
function findSpecialPrime($N)
{
    // Initially all numbers are
    // considered Primes.
    $sieve = array_fill(0, $N * 10, true);
 
    $sieve[0] = $sieve[1] = false;
    for ($i = 2; $i <= $N * 10; $i++)
    {
        if ($sieve[$i])
        {
 
            for ($j = $i * $i;
                 $j <= $N * 10; $j += $i)
            {
                $sieve[$j] = false;
            }
        }
    }
 
    // There is always an answer possible
    while (true)
    {
        // Checking if the number is a
        // special prime or not
        if (checkSpecialPrime($sieve, $N))
        {
             
            // If yes print the number
            // and break the loop.
            echo $N, "\n";
            break;
        }
         
        // Else increment the number.
        else
            $N++;
    }
}
 
// Driver code
$N = 379;
 
findSpecialPrime($N);
 
$N = 100;
findSpecialPrime($N);
 
// This code is contributed by Ryuga
?>

<script>
 
// javascript program to find the Smallest Special Prime
// which is greater than or equal to a given number  
// Function to check whether the number
// is a special prime or not
function checkSpecialPrime(sieve , num)
{
 
    // While number is not equal to zero
    while (num > 0)
    {
     
        // If the number is not prime
        // return false.
        if (sieve[num])
        {
            return false;
        }
 
        // Else remove the last digit
        // by dividing the number by 10.
        num = parseInt(num / 10);
    }
 
    // If the number has become zero
    // then the number is special prime,
    // hence return true
    return true;
}
 
// Function to find the Smallest Special Prime
// which is greater than or equal to a given number
function findSpecialPrime(N)
{
    var sieve = Array.from({length: N * 10 + 1}, (_, i) => false);
 
    // Initially all numbers are considered Primes.
    sieve[0] = true;
    sieve[1] = true;
    var i = 0, j = 0;
    for (i = 2; i <= N * 10; i++)
    {
        if (!sieve[i])
        {
            for (j = i * i; j <= N * 10; j += i)
            {
                sieve[j] = true;
            }
        }
    }
 
    // There is always an answer possible
    while (true)
    {
     
        // Checking if the number is a
        // special prime or not
        if (checkSpecialPrime(sieve, N))
        {
         
            // If yes print the number
            // and break the loop.
            document.write(N+"<br>");
            break;
        }
         
        // Else increment the number.
        else
            N++;
    }
}
 
// Driver code
var N = 379;
findSpecialPrime(N);
N = 100;
findSpecialPrime(N);
 
// This code is contributed by shikhasingrajput
</script>

379
233

Complejidad del tiempo: O(nlog(logn))

Espacio Auxiliar: O(n)