Encuentre N enteros distintos con GCD de secuencia como 1 y GCD de cada par mayor que 1

Dado un entero N , la tarea es encontrar una secuencia de N enteros positivos distintos tal que el Máximo Común Divisor de la secuencia sea 1 y el MCD de todos los posibles pares de elementos sea mayor que 1.

Entrada: N = 4
Salida: 84 60 105 70
Explicación: El MCD (84, 60, 105, 70) es 1 y el MCD de todos los pares de elementos posibles, es decir, {(84, 60), (84, 105), (84, 70), (60, 105), (60, 70), (105, 70)} es mayor que 1.

Entrada: N = 3
Salida: 6 10 15

Enfoque: este problema se puede resolver utilizando la estructura de datos establecida . La idea es elegir tres enteros de la forma (a*b, b*c, c*a) , ya que el MCD de los tres es 1 y el MCD de los tres por pares siempre es mayor que 1. Además, simplemente suma los múltiplos de los tres enteros hasta que la secuencia contenga el número requerido de enteros. Un conjunto de enteros de la forma (a*b, b*c, c*a) es (6, 10, 15) . Por lo tanto, agregue múltiplos de 6 , 10 y 15 a la secuencia e imprima el número requerido de enteros.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sequence of
// distinct integers with GCD equal
// to 1 and every pair has GCD > 1.
void findSequence(int N)
{
    // Special case
    if (N == 3) {
        cout << "6 10 15" << endl;
        return;
    }
 
    // Set to avoid duplicates
    set<int> s;
    s.insert(6);
    s.insert(10);
    s.insert(15);
 
    // Add multiples of 6
    for (int i = 12; i <= 10000; i += 6)
        s.insert(i);
 
    // Add multiples of 10
    for (int i = 20; i <= 10000; i += 10)
        s.insert(i);
 
    // Add multiples of 15
    for (int i = 30; i <= 10000; i += 15)
        s.insert(i);
     
      int cnt = 0;
 
    // Print first N numbers of set
    for (int x : s) {
        cout << x << " ";
        cnt++;
        if (cnt == N) {
            break;
        }
    }
}
 
// Driver Code
int main()
{
    int N = 3;
    findSequence(N);
 
    return 0;
}

// Java program for above approach
import java.util.*;
 
class GFG{
 
// Function to find the sequence of
// distinct integers with GCD equal
// to 1 and every pair has GCD > 1.
static void findSequence(int N)
{
     
    // Special case
    if (N == 3)
    {
        System.out.println("6 10 15");
        return;
    }
 
    // Set to avoid duplicates
    Set<Integer> s = new HashSet<Integer>();
    s.add(6);
    s.add(10);
    s.add(15);
 
    // Add multiples of 6
    for(int i = 12; i <= 10000; i += 6)
        s.add(i);
 
    // Add multiples of 10
    for(int i = 20; i <= 10000; i += 10)
        s.add(i);
 
    // Add multiples of 15
    for(int i = 30; i <= 10000; i += 15)
        s.add(i);
 
    int cnt = 0;
 
    // Print first N numbers of set
    for(Integer x : s)
    {
        System.out.print(x + " ");
        cnt++;
         
        if (cnt == N)
        {
            break;
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 3;
     
    findSequence(N);
}
}
 
// This code is contributed by Potta Lokesh

# python program for above approach
 
# Function to find the sequence of
# distinct integers with GCD equal
# to 1 and every pair has GCD > 1.
def findSequence(N):
 
    # Special case
    if (N == 3):
        print("6 10 15")
        return
 
    # Set to avoid duplicates
    s = set()
    s.add(6)
    s.add(10)
    s.add(15)
 
    # Add multiples of 6
    for i in range(12, 10001, 6):
        s.add(i)
 
    # Add multiples of 10
    for i in range(20, 10001, 10):
        s.add(i)
 
    # Add multiples of 15
    for i in range(30, 10001, 15):
        s.add(i)
 
    cnt = 0
 
    # Print first N numbers of set
    for x in s:
        print(x, end=" ")
        cnt += 1
        if (cnt == N):
            break
 
# Driver Code
if __name__ == "__main__":
 
    N = 3
    findSequence(N)
 
# This code is contributed by rakeshsahni

// C# program for above approach
using System;
using System.Collections.Generic;
class GFG {
 
    // Function to find the sequence of
    // distinct integers with GCD equal
    // to 1 and every pair has GCD > 1.
    static void findSequence(int N)
    {
 
        // Special case
        if (N == 3) {
            Console.WriteLine("6 10 15");
            return;
        }
 
        // Set to avoid duplicates
        HashSet<int> s = new HashSet<int>();
        s.Add(6);
        s.Add(10);
        s.Add(15);
 
        // Add multiples of 6
        for (int i = 12; i <= 10000; i += 6)
            s.Add(i);
 
        // Add multiples of 10
        for (int i = 20; i <= 10000; i += 10)
            s.Add(i);
 
        // Add multiples of 15
        for (int i = 30; i <= 10000; i += 15)
            s.Add(i);
 
        int cnt = 0;
 
        // Print first N numbers of set
        foreach(int x in s)
        {
            Console.Write(x + " ");
            cnt++;
 
            if (cnt == N) {
                break;
            }
        }
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int N = 3;
 
        findSequence(N);
    }
}
 
// Thiss code is contributed by ukasp.

<script>
// Javascript program for above approach
 
// Function to find the sequence of
// distinct integers with GCD equal
// to 1 and every pair has GCD > 1.
function findSequence(N)
{
 
    // Special case
    if (N == 3) {
        document.write("6 10 15");
        return;
    }
 
    // Set to avoid duplicates
    let s = new Set();
    s.add(6);
    s.add(10);
    s.add(15);
 
    // Add multiples of 6
    for (let i = 12; i <= 10000; i += 6)
        s.add(i);
 
    // Add multiples of 10
    for (let i = 20; i <= 10000; i += 10)
        s.add(i);
 
    // Add multiples of 15
    for (let i = 30; i <= 10000; i += 15)
        s.add(i);
 
    let cnt = 0;
 
    // Print first N numbers of set
    for (x of s) {
        document.write(x + " ");
        cnt++;
        if (cnt == N) {
            break;
        }
    }
}
 
// Driver Code
let N = 3;
findSequence(N);
 
// This code is contributed by gfgking.
</script>

6 10 15

Complejidad de tiempo: O(N*log N) 
Espacio auxiliar: O(N)