Dado un número entero N , la tarea es encontrar el número compuesto más pequeño que no sea divisible por los primeros N números primos .
Ejemplos:
Entrada: N = 3
Salida: 49
Explicación:
Los primeros 3 números primos son {2, 3, 5}. El entero compuesto más pequeño que no es divisible por 2, 3 o 5 es 49.Entrada: N = 2
Salida: 25
Explicación:
Los 2 primeros números primos son {2, 3}. El entero compuesto más pequeño que no es divisible ni por 2 ni por 3 es 25.
Enfoque ingenuo: el enfoque más simple para resolver el problema es verificar las siguientes condiciones para cada número a partir de 2:
- Condición 1: Comprobar si el número actual es primo o no. Si es primo, repita el proceso para el siguiente número. De lo contrario, si el número es compuesto, verifique las siguientes condiciones:
- Condición 2: Encuentra los primeros N números primos y comprueba si este número compuesto no es divisible por cada uno de ellos.
- Si el número actual cumple con las dos condiciones anteriores, imprima ese número como la respuesta requerida.
Complejidad temporal: O(M 3 N), donde M denota el número compuesto que cumple la condición.
Espacio Auxiliar: O(N), para almacenar los N números primos.
Enfoque eficiente: el problema dado se puede resolver utilizando la siguiente observación:
El primer número compuesto que no es divisible por ninguno de los primeros N números primos = ((N + 1) el número primo) 2
Ilustración:
Para N = 2
=> Los 2 primeros números primos son {2, 3}
=> (N + 1) el número primo es 5
=> Se puede observar que todos los números no primos hasta el 24 {4, 6, 8 , 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24} son divisibles por 2, por 3 o por ambos.
=> El siguiente número compuesto {25} es divisible solo por 5.
=> Por lo tanto, se puede concluir que el primer número compuesto que no es divisible por ninguno de los primeros N números primos es el cuadrado del (N + 1) número primo.
La idea es encontrar el (N+1) número primo usando la criba de Eratóstenes e imprimir el cuadrado del (N+1) número primo como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Initializing the max value
#define MAX_SIZE 1000005
// Function to generate N prime numbers
// using Sieve of Eratosthenes
void SieveOfEratosthenes(
vector<int>& StorePrimes)
{
// Stores the primes
bool IsPrime[MAX_SIZE];
// Setting all numbers to be prime initially
memset(IsPrime, true, sizeof(IsPrime));
for (int p = 2; p * p < MAX_SIZE; p++) {
// If a prime number is encountered
if (IsPrime[p] == true) {
// Set all its multiples as composites
for (int i = p * p; i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Store all the prime numbers
for (int p = 2; p < MAX_SIZE; p++)
if (IsPrime[p])
StorePrimes.push_back(p);
}
// Function to find the square of
// the (N + 1)-th prime number
int Smallest_non_Prime(
vector<int> StorePrimes,
int N)
{
int x = StorePrimes[N];
return x * x;
}
// Driver Code
int main()
{
int N = 3;
// Stores all prime numbers
vector<int> StorePrimes;
SieveOfEratosthenes(StorePrimes);
cout << Smallest_non_Prime(StorePrimes, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.Arrays;
import java.util.Vector;
class GFG{
// Initializing the max value
static final int MAX_SIZE = 1000005;
// Function to generate N prime numbers
// using Sieve of Eratosthenes
static void SieveOfEratosthenes(
Vector<Integer> StorePrimes)
{
// Stores the primes
boolean []IsPrime = new boolean[MAX_SIZE];
// Setting all numbers to be prime initially
Arrays.fill(IsPrime, true);
for(int p = 2; p * p < MAX_SIZE; p++)
{
// If a prime number is encountered
if (IsPrime[p] == true)
{
// Set all its multiples as composites
for(int i = p * p; i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Store all the prime numbers
for(int p = 2; p < MAX_SIZE; p++)
if (IsPrime[p])
StorePrimes.add(p);
}
// Function to find the square of
// the (N + 1)-th prime number
static int Smallest_non_Prime(
Vector<Integer> StorePrimes,
int N)
{
int x = StorePrimes.get(N);
return x * x;
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
// Stores all prime numbers
Vector<Integer> StorePrimes = new Vector<Integer>();
SieveOfEratosthenes(StorePrimes);
System.out.print(Smallest_non_Prime(StorePrimes, N));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to implement # the above approach # Initializing the max value MAX_SIZE = 1000005 # Function to generate N prime numbers # using Sieve of Eratosthenes def SieveOfEratosthenes(StorePrimes): # Stores the primes IsPrime = [True for i in range(MAX_SIZE)] p = 2 while (p * p < MAX_SIZE): # If a prime number is encountered if (IsPrime[p] == True): # Set all its multiples as composites for i in range(p * p, MAX_SIZE, p): IsPrime[i] = False p += 1 # Store all the prime numbers for p in range(2, MAX_SIZE): if (IsPrime[p]): StorePrimes.append(p) # Function to find the square of # the (N + 1)-th prime number def Smallest_non_Prime(StorePrimes, N): x = StorePrimes[N] return x * x # Driver Code if __name__ == '__main__': N = 3 # Stores all prime numbers StorePrimes = [] SieveOfEratosthenes(StorePrimes) print(Smallest_non_Prime(StorePrimes, N)) # This code is contributed by bgangwar59
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Initializing the max value
static readonly int MAX_SIZE = 1000005;
// Function to generate N prime numbers
// using Sieve of Eratosthenes
static void SieveOfEratosthenes(
List<int> StorePrimes)
{
// Stores the primes
bool []IsPrime = new bool[MAX_SIZE];
// Setting all numbers to be prime initially
for(int i = 0; i < MAX_SIZE; i++)
IsPrime[i] = true;
for(int p = 2; p * p < MAX_SIZE; p++)
{
// If a prime number is encountered
if (IsPrime[p] == true)
{
// Set all its multiples as composites
for(int i = p * p; i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Store all the prime numbers
for(int p = 2; p < MAX_SIZE; p++)
if (IsPrime[p])
StorePrimes.Add(p);
}
// Function to find the square of
// the (N + 1)-th prime number
static int Smallest_non_Prime(
List<int> StorePrimes,
int N)
{
int x = StorePrimes[N];
return x * x;
}
// Driver Code
public static void Main(String[] args)
{
int N = 3;
// Stores all prime numbers
List<int> StorePrimes = new List<int>();
SieveOfEratosthenes(StorePrimes);
Console.Write(Smallest_non_Prime(StorePrimes, N));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript Program to implement
// the above approach
// Initializing the max value
var MAX_SIZE = 1000005;
// Function to generate N prime numbers
// using Sieve of Eratosthenes
function SieveOfEratosthenes(StorePrimes)
{
// Stores the primes
var IsPrime = Array(MAX_SIZE).fill(true);
var p,i;
for(p = 2; p * p < MAX_SIZE; p++) {
// If a prime number is encountered
if (IsPrime[p] == true) {
// Set all its multiples as composites
for(i = p * p; i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Store all the prime numbers
for (p = 2; p < MAX_SIZE; p++)
if (IsPrime[p])
StorePrimes.push(p);
}
// Function to find the square of
// the (N + 1)-th prime number
function Smallest_non_Prime(StorePrimes, N)
{
var x = StorePrimes[N];
return x * x;
}
// Driver Code
N = 3;
// Stores all prime numbers
var StorePrimes = [];
SieveOfEratosthenes(StorePrimes);
document.write(Smallest_non_Prime(StorePrimes, N));
</script>
49
Complejidad de tiempo: O(MAX_SIZE log (log MAX_SIZE)), donde MAX_SIZE denota el límite superior hasta el cual se generan N números primos.
Espacio Auxiliar: O(MAX_SIZE)
Publicación traducida automáticamente
Artículo escrito por jayendrasingh420 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA