Encuentra todos los números primos de un número dado de dígitos

Dado un entero D , la tarea es encontrar todos los números primos que tienen D dígitos.
 

Ejemplos:  
Entrada: D = 1 
Salida: 2 3 5 7 
Entrada: D = 2 
Salida: 11 13 17 19 23 29 31 37 41 43 47 53 61 67 71 73 79 83 89 97 
 

Enfoque: Los números con dígitos D se encuentran en el rango [10 ^{(D – 1)} , 10 ^D – 1] . Entonces, verifique todos los números en este intervalo y para verificar si el número es primo o no, use la Criba de Eratóstenes para generar todos los números primos.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int sz = 1e5;
bool isPrime[sz + 1];
 
// Function for Sieve of Eratosthenes
void sieve()
{
    memset(isPrime, true, sizeof(isPrime));
 
    isPrime[0] = isPrime[1] = false;
 
    for (int i = 2; i * i <= sz; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < sz; j += i) {
                isPrime[j] = false;
            }
        }
    }
}
 
// Function to print all the prime
// numbers with d digits
void findPrimesD(int d)
{
 
    // Range to check integers
    int left = pow(10, d - 1);
    int right = pow(10, d) - 1;
 
    // For every integer in the range
    for (int i = left; i <= right; i++) {
 
        // If the current integer is prime
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
}
 
// Driver code
int main()
{
 
    // Generate primes
    sieve();
    int d = 1;
    findPrimesD(d);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
static int sz = 100000;
static boolean isPrime[] = new boolean[sz + 1];
 
// Function for Sieve of Eratosthenes
static void sieve()
{
    for(int i = 0; i <= sz; i++)
    isPrime[i] = true;
     
    isPrime[0] = isPrime[1] = false;
 
    for (int i = 2; i * i <= sz; i++)
    {
        if (isPrime[i])
        {
            for (int j = i * i; j < sz; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
}
 
// Function to print all the prime
// numbers with d digits
static void findPrimesD(int d)
{
 
    // Range to check integers
    int left = (int)Math.pow(10, d - 1);
    int right = (int)Math.pow(10, d) - 1;
 
    // For every integer in the range
    for (int i = left; i <= right; i++)
    {
 
        // If the current integer is prime
        if (isPrime[i])
        {
            System.out.print(i + " ");
        }
    }
}
 
// Driver code
public static void main(String args[])
{
 
    // Generate primes
    sieve();
    int d = 1;
    findPrimesD(d);
}
}
 
// This code is contributed by Arnab Kundu

# Python 3 implementation of the approach
from math import sqrt, pow
sz = 100005
isPrime = [True for i in range(sz + 1)]
 
# Function for Sieve of Eratosthenes
def sieve():
    isPrime[0] = isPrime[1] = False
 
    for i in range(2, int(sqrt(sz)) + 1, 1):
        if (isPrime[i]):
            for j in range(i * i, sz, i):
                isPrime[j] = False
 
# Function to print all the prime
# numbers with d digits
def findPrimesD(d):
     
    # Range to check integers
    left = int(pow(10, d - 1))
    right = int(pow(10, d) - 1)
 
    # For every integer in the range
    for i in range(left, right + 1, 1):
         
        # If the current integer is prime
        if (isPrime[i]):
            print(i, end = " ")
         
# Driver code
if __name__ == '__main__':
     
    # Generate primes
    sieve()
    d = 1
    findPrimesD(d)
     
# This code is contributed by Surendra_Gangwar

// C# implementation of the approach
using System;
 
class GFG
{
     
static int sz = 100000;
static bool []isPrime = new bool[sz + 1];
 
// Function for Sieve of Eratosthenes
static void sieve()
{
    for(int i = 0; i <= sz; i++)
    isPrime[i] = true;
     
    isPrime[0] = isPrime[1] = false;
 
    for (int i = 2; i * i <= sz; i++)
    {
        if (isPrime[i])
        {
            for (int j = i * i; j < sz; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
}
 
// Function to print all the prime
// numbers with d digits
static void findPrimesD(int d)
{
 
    // Range to check integers
    int left = (int)Math.Pow(10, d - 1);
    int right = (int)Math.Pow(10, d) - 1;
 
    // For every integer in the range
    for (int i = left; i <= right; i++)
    {
 
        // If the current integer is prime
        if (isPrime[i])
        {
            Console.Write(i + " ");
        }
    }
}
 
// Driver code
static public void Main ()
{
     
    // Generate primes
    sieve();
    int d = 1;
    findPrimesD(d);
 
}
}
 
// This code is contributed by ajit.

<script>
    // Javascript implementation of the approach
     
    let sz = 100000;
    let isPrime = new Array(sz + 1);
    isPrime.fill(false);
 
    // Function for Sieve of Eratosthenes
    function sieve()
    {
        for(let i = 0; i <= sz; i++)
            isPrime[i] = true;
 
        isPrime[0] = isPrime[1] = false;
 
        for (let i = 2; i * i <= sz; i++)
        {
            if (isPrime[i])
            {
                for (let j = i * i; j < sz; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }
    }
 
    // Function to print all the prime
    // numbers with d digits
    function findPrimesD(d)
    {
 
        // Range to check integers
        let left = Math.pow(10, d - 1);
        let right = Math.pow(10, d) - 1;
 
        // For every integer in the range
        for (let i = left; i <= right; i++)
        {
 
            // If the current integer is prime
            if (isPrime[i])
            {
                document.write(i + " ");
            }
        }
    }
     
    // Generate primes
    sieve();
    let d = 1;
    findPrimesD(d);
 
// This code is contributed by suresh07.
</script>

2 3 5 7

Complejidad de tiempo: O(sqrt(10 ⁵ ) + d)

Espacio Auxiliar: O(10 ⁵ )