Dado un entero positivo N, la tarea es encontrar el número compuesto N.
Ejemplos:
Entrada: N = 1
Salida: 4Entrada: N = 3
Salida: 8
Planteamiento: El problema dado se puede resolver utilizando el concepto de Criba de Eratóstenes . Siga los pasos a continuación para resolver el problema:
- Marque todos los números primos hasta 10 5 en una array booleana, digamos i sPrime[] usando Sieve of Eratosthenes.
- Inicialice una array , digamos composites[] que almacena todos los números compuestos.
- Recorra la array isPrime[] usando la variable i , si el valor de isPrime[i] es falso, luego inserte el número i en la array composites[] .
- Después de completar los pasos anteriores, imprima el valor composites[N – 1] como el N número compuesto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define MAX_SIZE 1000005
// Function to find the Nth Composite
// Numbers using Sieve of Eratosthenes
int NthComposite(int N)
{
// Sieve of prime numbers
bool IsPrime[MAX_SIZE];
// Initialize the array to true
memset(IsPrime, true, sizeof(IsPrime));
// Iterate over the range [2, MAX_SIZE]
for (int p = 2;
p * p < MAX_SIZE; p++) {
// If IsPrime[p] is true
if (IsPrime[p] == true) {
// Iterate over the
// range [p * p, MAX_SIZE]
for (int i = p * p;
i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Stores the list of composite numbers
vector<int> Composites;
// Iterate over the range [4, MAX_SIZE]
for (int p = 4; p < MAX_SIZE; p++)
// If i is not prime
if (!IsPrime[p])
Composites.push_back(p);
// Return Nth Composite Number
return Composites[N - 1];
}
// Driver Code
int main()
{
int N = 4;
cout << NthComposite(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to find the Nth Composite
// Numbers using Sieve of Eratosthenes
public static int NthComposite(int N)
{
int MAX_SIZE = 1000005;
// Sieve of prime numbers
boolean[] IsPrime = new boolean[MAX_SIZE];
// Initialize the array to true
Arrays.fill(IsPrime, true);
// Iterate over the range [2, MAX_SIZE]
for (int p = 2; p * p < MAX_SIZE; p++) {
// If IsPrime[p] is true
if (IsPrime[p] == true) {
// Iterate over the
// range [p * p, MAX_SIZE]
for (int i = p * p;
i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Stores the list of composite numbers
Vector<Integer> Composites = new Vector<Integer>();
// Iterate over the range [4, MAX_SIZE]
for (int p = 4; p < MAX_SIZE; p++)
// If i is not prime
if (!IsPrime[p])
Composites.add(p);
// Return Nth Composite Number
return Composites.get(N - 1);
}
// Driver Code
public static void main(String args[])
{
int N = 4;
System.out.println(NthComposite(N));
}
}
// This code is contributed by SoumikMondal.
Python3
# Python3 program for the above approach # Function to find the Nth Composite # Numbers using Sieve of Eratosthenes def NthComposite(N): # Sieve of prime numbers IsPrime = [True]*1000005 # Iterate over the range [2, 1000005] for p in range(2, 1000005): if p * p > 1000005: break # If IsPrime[p] is true if (IsPrime[p] == True): # Iterate over the # range [p * p, 1000005] for i in range(p*p,1000005,p): IsPrime[i] = False # Stores the list of composite numbers Composites = [] # Iterate over the range [4, 1000005] for p in range(4,1000005): # If i is not prime if (not IsPrime[p]): Composites.append(p) # Return Nth Composite Number return Composites[N - 1] # Driver Code if __name__ == '__main__': N = 4 print (NthComposite(N)) # This code is contributed by mohit kumar 29.
C#
using System;
using System.Collections.Generic;
public class GFG{
// Function to find the Nth Composite
// Numbers using Sieve of Eratosthenes
public static int NthComposite(int N)
{
int MAX_SIZE = 1000005;
// Sieve of prime numbers
bool[] IsPrime = new bool[MAX_SIZE];
// Initialize the array to true
Array.Fill(IsPrime, true);
// Iterate over the range [2, MAX_SIZE]
for (int p = 2; p * p < MAX_SIZE; p++) {
// If IsPrime[p] is true
if (IsPrime[p] == true) {
// Iterate over the
// range [p * p, MAX_SIZE]
for (int i = p * p;
i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Stores the list of composite numbers
List<int> Composites = new List<int>();
// Iterate over the range [4, MAX_SIZE]
for (int p = 4; p < MAX_SIZE; p++)
// If i is not prime
if (!IsPrime[p])
Composites.Add(p);
// Return Nth Composite Number
return Composites[N - 1];
}
// Driver Code
static public void Main ()
{
int N = 4;
Console.WriteLine(NthComposite(N));
}
}
// This code is contributed by patel2127
Javascript
<script>
// JavaScript program for the above approach
let MAX_SIZE = 1000005;
// Function to find the Nth Composite
// Numbers using Sieve of Eratosthenes
function NthComposite( N)
{
// Sieve of prime numbers
let IsPrime = [];
// Initialize the array to true
for(let i = 0;i<MAX_SIZE;i++)
IsPrime.push(true);
// Iterate over the range [2, MAX_SIZE]
for (let p = 2;
p * p < MAX_SIZE; p++) {
// If IsPrime[p] is true
if (IsPrime[p] == true) {
// Iterate over the
// range [p * p, MAX_SIZE]
for (let i = p * p;
i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Stores the list of composite numbers
let Composites = [];
// Iterate over the range [4, MAX_SIZE]
for (let p = 4; p < MAX_SIZE; p++)
// If i is not prime
if (!IsPrime[p])
Composites.push(p);
// Return Nth Composite Number
return Composites[N - 1];
}
// Driver Code
let N = 4;
document.write(NthComposite(N));
</script>
Producción:
9
Complejidad de Tiempo: O(N + M * log(log(M)), donde [2, M] es el rango donde se realiza el Cribado de Eratóstenes.
Espacio Auxiliar: O(N)