Dadas Q consultas donde cada consulta consta de un entero D , la tarea es encontrar el número primo más pequeño y el más grande con D dígitos. Si no existe tal número primo, imprima -1 .
Ejemplos:
Entrada: Q[] = {2, 5}
Salida:
11 97
10007 99991
Entrada: Q[] = {4, 3, 1}
Salida:
1009 9973
101 997
1 7
Acercarse:
- Los números de dígitos D comienzan en 10 (D – 1) y terminan en 10 D – 1 .
- Ahora, la tarea es encontrar el número primo más pequeño y el más grande de este rango.
- Para responder a una serie de consultas sobre números primos, se puede utilizar la criba de Eratóstenes para responder si un número es primo o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
bool prime[MAX + 1];
void SieveOfEratosthenes()
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= MAX; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (int i = p * p; i <= MAX; i += p)
prime[i] = false;
}
}
}
// Function to return the smallest prime
// number with d digits
int smallestPrime(int d)
{
int l = pow(10, d - 1);
int r = pow(10, d) - 1;
for (int i = l; i <= r; i++) {
// check if prime
if (prime[i]) {
return i;
}
}
return -1;
}
// Function to return the largest prime
// number with d digits
int largestPrime(int d)
{
int l = pow(10, d - 1);
int r = pow(10, d) - 1;
for (int i = r; i >= l; i--) {
// check if prime
if (prime[i]) {
return i;
}
}
return -1;
}
// Driver code
int main()
{
SieveOfEratosthenes();
int queries[] = { 2, 5 };
int q = sizeof(queries) / sizeof(queries[0]);
// Perform queries
for (int i = 0; i < q; i++) {
cout << smallestPrime(queries[i]) << " "
<< largestPrime(queries[i]) << endl;
}
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 100000;
static boolean []prime = new boolean[MAX + 1];
static void SieveOfEratosthenes()
{
// Create a boolean array "prime[0..n]" and
// initialize all entries it as true.
// A value in prime[i] will finally be false
// if i is Not a prime, else true.
for (int i = 0; i < MAX + 1; i++)
{
prime[i] = true;
}
for (int p = 2; p * p <= MAX; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (int i = p * p; i <= MAX; i += p)
prime[i] = false;
}
}
}
// Function to return the smallest prime
// number with d digits
static int smallestPrime(int d)
{
int l = (int) Math.pow(10, d - 1);
int r = (int) Math.pow(10, d) - 1;
for (int i = l; i <= r; i++)
{
// check if prime
if (prime[i])
{
return i;
}
}
return -1;
}
// Function to return the largest prime
// number with d digits
static int largestPrime(int d)
{
int l = (int) Math.pow(10, d - 1);
int r = (int) Math.pow(10, d) - 1;
for (int i = r; i >= l; i--)
{
// check if prime
if (prime[i])
{
return i;
}
}
return -1;
}
// Driver code
public static void main(String[] args)
{
SieveOfEratosthenes();
int queries[] = { 2, 5 };
int q = queries.length;
// Perform queries
for (int i = 0; i < q; i++)
{
System.out.println(smallestPrime(queries[i]) + " " +
largestPrime(queries[i]));
}
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach from math import sqrt MAX = 100000 # Create a boolean array "prime[0..n]" and # initialize all entries it as true. # A value in prime[i] will finally be false # if i is Not a prime, else true. prime = [True] * (MAX + 1) def SieveOfEratosthenes() : for p in range(2, int(sqrt(MAX)) + 1) : # If prime[p] is not changed, # then it is a prime if (prime[p] == True) : # Update all multiples of p greater than or # equal to the square of it # numbers which are multiple of p and are # less than p^2 are already been marked. for i in range(p * p, MAX + 1, p) : prime[i] = False; # Function to return the smallest prime # number with d digits def smallestPrime(d) : l = 10 ** (d - 1); r = (10 ** d) - 1; for i in range(l, r + 1) : # check if prime if (prime[i]) : return i; return -1; # Function to return the largest prime # number with d digits def largestPrime(d) : l = 10 ** (d - 1); r = (10 ** d) - 1; for i in range(r, l , -1) : # check if prime if (prime[i]) : return i; return -1; # Driver code if __name__ == "__main__" : SieveOfEratosthenes(); queries = [ 2, 5 ]; q = len(queries); # Perform queries for i in range(q) : print(smallestPrime(queries[i]), " ", largestPrime(queries[i])); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 100000;
static bool []prime = new bool[MAX + 1];
static void SieveOfEratosthenes()
{
// Create a boolean array "prime[0..n]" and
// initialize all entries it as true.
// A value in prime[i] will finally be false
// if i is Not a prime, else true.
for (int i = 0; i < MAX + 1; i++)
{
prime[i] = true;
}
for (int p = 2; p * p <= MAX; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p greater than
// or equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (int i = p * p; i <= MAX; i += p)
prime[i] = false;
}
}
}
// Function to return the smallest prime
// number with d digits
static int smallestPrime(int d)
{
int l = (int) Math.Pow(10, d - 1);
int r = (int) Math.Pow(10, d) - 1;
for (int i = l; i <= r; i++)
{
// check if prime
if (prime[i])
{
return i;
}
}
return -1;
}
// Function to return the largest prime
// number with d digits
static int largestPrime(int d)
{
int l = (int) Math.Pow(10, d - 1);
int r = (int) Math.Pow(10, d) - 1;
for (int i = r; i >= l; i--)
{
// check if prime
if (prime[i])
{
return i;
}
}
return -1;
}
// Driver code
public static void Main(String[] args)
{
SieveOfEratosthenes();
int []queries = { 2, 5 };
int q = queries.Length;
// Perform queries
for (int i = 0; i < q; i++)
{
Console.WriteLine(smallestPrime(queries[i]) + " " +
largestPrime(queries[i]));
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
const MAX = 100000;
// Create a boolean array
// "prime[0..n]" and initialize
// all entries it as true.
// A value in prime[i] will
// finally be false if i is Not a prime,
// else true.
let prime = new Array(MAX + 1).fill(true);
function SieveOfEratosthenes()
{
for (let p = 2; p * p <= MAX; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true) {
// Update all multiples of p
// greater than or
// equal to the square of it
// numbers which are multiple
// of p and are
// less than p^2 are already
// been marked.
for (let i = p * p; i <= MAX; i += p)
prime[i] = false;
}
}
}
// Function to return the smallest prime
// number with d digits
function smallestPrime(d)
{
let l = Math.pow(10, d - 1);
let r = Math.pow(10, d) - 1;
for (let i = l; i <= r; i++) {
// check if prime
if (prime[i]) {
return i;
}
}
return -1;
}
// Function to return the largest prime
// number with d digits
function largestPrime(d)
{
let l = Math.pow(10, d - 1);
let r = Math.pow(10, d) - 1;
for (let i = r; i >= l; i--) {
// check if prime
if (prime[i]) {
return i;
}
}
return -1;
}
// Driver code
SieveOfEratosthenes();
let queries = [ 2, 5 ];
let q = queries.length;
// Perform queries
for (let i = 0; i < q; i++) {
document.write(smallestPrime(queries[i]) + " "
+ largestPrime(queries[i]) + "<br>");
}
</script>
Producción:
11 97 10007 99991
Complejidad del tiempo: O(MAX*log(log(MAX)) + q*(r – l))
Espacio Auxiliar: O(MAX)