Dado un número entero N , la tarea es generar una array de tamaño N con las siguientes propiedades:
- No hay dos elementos que se dividan entre sí.
- Todo subconjunto impar tiene una suma impar y todo subconjunto par tiene una suma par.
Ejemplos:
Entrada: N = 3
Salida: 3 5 7
No hay dos elementos que se dividan entre sí y la suma
de todos los subconjuntos impares {3}, {5}, {7} y {3, 5, 7} es impar.
La suma de todos los subconjuntos pares es par, es decir, {3, 5}, {3, 7} y {5, 7}
Entrada: N = 6
Salida: 3 5 7 11 13 17
Enfoque: Para satisfacer la condición cuando cada subconjunto impar tiene una suma impar e incluso un subconjunto tiene una suma par, cada elemento tiene que ser impar y para que dos elementos no se dividan entre sí deben ser primos. Entonces, la tarea ahora es encontrar los primeros N números primos impares.
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 1000000
// 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.
bool prime[MAX + 1];
void SieveOfEratosthenes()
{
memset(prime, true, sizeof(prime));
prime[1] = false;
for (int p = 2; p * p <= MAX; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Set all multiples of p to non-prime
for (int i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
}
}
// Function to find the first
// n odd prime numbers
void solve(int n)
{
// To store the current count
// of prime numbers
int count = 0;
// Starting with 3 as 2 is
// an even prime number
for (int i = 3; count < n; i++) {
// If i is prime
if (prime[i]) {
// Print i and increment count
cout << i << " ";
count++;
}
}
}
// Driver code
int main()
{
// Create the sieve
SieveOfEratosthenes();
int n = 6;
solve(n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 1000000;
// 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.
static boolean []prime = new boolean[MAX + 1];
static void SieveOfEratosthenes()
{
for (int i = 0; i <= MAX; i ++)
prime[i] = true;
prime[1] = false;
for (int p = 2; p * p <= MAX; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Set all multiples of p to non-prime
for (int i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
}
}
// Function to find the first
// n odd prime numbers
static void solve(int n)
{
// To store the current count
// of prime numbers
int count = 0;
// Starting with 3 as 2 is
// an even prime number
for (int i = 3; count < n; i++)
{
// If i is prime
if (prime[i])
{
// Print i and increment count
System.out.print(i + " ");
count++;
}
}
}
// Driver code
public static void main(String[] args)
{
// Create the sieve
SieveOfEratosthenes();
int n = 6;
solve(n);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach from math import sqrt MAX = 1000000 # 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() : prime[1] = False; for p in range(2, int(sqrt(MAX)) + 1) : # If prime[p] is not changed, # then it is a prime if (prime[p] == True) : # Set all multiples of p to non-prime for i in range(p * 2, MAX + 1, p) : prime[i] = False; # Function to find the first # n odd prime numbers def solve(n) : # To store the current count # of prime numbers count = 0; i = 3; # Starting with 3 as 2 is # an even prime number while count < n : # If i is prime if (prime[i]) : # Print i and increment count print(i, end = " "); count += 1; i += 1 # Driver code if __name__ == "__main__" : # Create the sieve SieveOfEratosthenes(); n = 6; solve(n); # This code is contributed by AnkitRai01
C#
// C# implementation of the above approach
using System;
class GFG
{
static int MAX = 1000000;
// 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.
static bool []prime = new bool[MAX + 1];
static void SieveOfEratosthenes()
{
for (int i = 0; i <= MAX; i ++)
prime[i] = true;
prime[1] = false;
for (int p = 2; p * p <= MAX; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Set all multiples of p to non-prime
for (int i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
}
}
// Function to find the first
// n odd prime numbers
static void solve(int n)
{
// To store the current count
// of prime numbers
int count = 0;
// Starting with 3 as 2 is
// an even prime number
for (int i = 3; count < n; i++)
{
// If i is prime
if (prime[i])
{
// Print i and increment count
Console.Write(i + " ");
count++;
}
}
}
// Driver code
public static void Main(String[] args)
{
// Create the sieve
SieveOfEratosthenes();
int n = 6;
solve(n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
const MAX = 1000000;
// 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()
{
prime[1] = false;
for (let p = 2; p * p <= MAX; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Set all multiples of p to non-prime
for (let i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
}
}
// Function to find the first
// n odd prime numbers
function solve(n)
{
// To store the current count
// of prime numbers
let count = 0;
// Starting with 3 as 2 is
// an even prime number
for (let i = 3; count < n; i++) {
// If i is prime
if (prime[i]) {
// Print i and increment count
document.write(i + " ");
count++;
}
}
}
// Driver code
// Create the sieve
SieveOfEratosthenes();
let n = 6;
solve(n);
</script>
Producción:
3 5 7 11 13 17
Complejidad temporal: O(n + MAX 3/2 )
Espacio Auxiliar: O(MAX)