Dado un número entero N , elija repetidamente dos números enteros distintos del rango de 2 a N y si se encuentra que su GCD es mayor que 1, insértelos en el mismo conjunto, tanto como sea posible. Los conjuntos formados en Relación de Equivalencia . Por lo tanto, si los enteros a y b están en el mismo conjunto y los enteros b y c están en el mismo conjunto, entonces se dice que los enteros a y c también están en el mismo grupo. La tarea es encontrar el número total de tales conjuntos que se pueden formar.
Ejemplos:
Entrada: N = 3
Salida: 2
Explicación: Los conjuntos formados son: {2}, {3}. No se pueden poner en el mismo conjunto porque su MCD es 1.Entrada: N = 9
Salida: 3
Los conjuntos formados son: {2, 3, 4, 6, 8, 9}, {5}, {7}
Como {2, 4, 6, 8} se encuentra en el mismo conjunto y {3 , 6, 9} también se encuentra en el mismo conjunto. Por lo tanto, todos estos se encuentran juntos en un conjunto, porque 6 es el elemento común en ambos conjuntos.
Planteamiento: La idea para resolver el problema se basa en la siguiente observación de que todos los números menores o iguales a N/2 pertenecen al mismo conjunto porque si en ellos se multiplica 2, serán números pares y tiene MCD mayor que 1 con 2 _ Entonces los conjuntos restantes están formados por números mayores que N/2 y son primos porque si no son primos entonces hay un número menor o igual que N/2 que es el divisor de ese número. Los números primos del 2 al N se pueden encontrar usando la Tamiz de Eratóstenes .
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;
bool prime[100001];
// Sieve of Eratosthenes to find
// primes less than or equal to N
void SieveOfEratosthenes(int n)
{
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= n; p++) {
if (prime[p] == true) {
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to find number of Sets
void NumberofSets(int N)
{
SieveOfEratosthenes(N);
// Handle Base Case
if (N == 2) {
cout << 1 << endl;
}
else if (N == 3) {
cout << 2 << endl;
}
else {
// Set which contains less
// than or equal to N/2
int ans = 1;
// Number greater than N/2 and
// are prime increment it by 1
for (int i = N / 2 + 1; i <= N; i++) {
// If the number is prime
// Increment answer by 1
if (prime[i]) {
ans += 1;
}
}
cout << ans << endl;
}
}
// Driver Code
int main()
{
// Input
int N = 9;
// Function Call
NumberofSets(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static boolean prime[] = new boolean[100001];
// Sieve of Eratosthenes to find
// primes less than or equal to N
static void SieveOfEratosthenes(int n)
{
Arrays.fill(prime, true);
for(int p = 2; p * p <= n; p++)
{
if (prime[p] == true)
{
for(int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to find number of Sets
static void NumberofSets(int N)
{
SieveOfEratosthenes(N);
// Handle Base Case
if (N == 2)
{
System.out.print(1);
}
else if (N == 3)
{
System.out.print(2);
}
else
{
// Set which contains less
// than or equal to N/2
int ans = 1;
// Number greater than N/2 and
// are prime increment it by 1
for(int i = N / 2 + 1; i <= N; i++)
{
// If the number is prime
// Increment answer by 1
if (prime[i])
{
ans += 1;
}
}
System.out.print(ans);
}
}
// Driver Code
public static void main(String[] args)
{
// Input
int N = 9;
// Function Call
NumberofSets(N);
}
}
// This code is contributed by code_hunt
Python3
# Python3 program for the above approach prime = [True] * 100001 # Sieve of Eratosthenes to find # primes less than or equal to N def SieveOfEratosthenes(n): global prime for p in range(2, n + 1): if p * p > n: break if (prime[p] == True): for i in range(p * p, n + 1, p): prime[i] = False # Function to find number of Sets def NumberofSets(N): SieveOfEratosthenes(N) # Handle Base Case if (N == 2): print(1) elif (N == 3): print(2) else: # Set which contains less # than or equal to N/2 ans = 1 # Number greater than N/2 and # are prime increment it by 1 for i in range(N // 2, N + 1): # If the number is prime # Increment answer by 1 if (prime[i]): ans += 1 print(ans) # Driver Code if __name__ == '__main__': # Input N = 9 # Function Call NumberofSets(N) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static bool []prime = new bool[100001];
// Sieve of Eratosthenes to find
// primes less than or equal to N
static void SieveOfEratosthenes(int n)
{
for(int i=0;i<100001;i++)
prime[i] = true;
for (int p = 2; p * p <= n; p++) {
if (prime[p] == true) {
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to find number of Sets
static void NumberofSets(int N)
{
SieveOfEratosthenes(N);
// Handle Base Case
if (N == 2) {
Console.Write(1);
}
else if (N == 3) {
Console.Write(2);
}
else {
// Set which contains less
// than or equal to N/2
int ans = 1;
// Number greater than N/2 and
// are prime increment it by 1
for (int i = N / 2 + 1; i <= N; i++) {
// If the number is prime
// Increment answer by 1
if (prime[i]) {
ans += 1;
}
}
Console.Write(ans);
}
}
// Driver Code
public static void Main()
{
// Input
int N = 9;
// Function Call
NumberofSets(N);
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// Javascript program for the above approach
let prime = new Array(100001);
// Sieve of Eratosthenes to find
// primes less than or equal to N
function SieveOfEratosthenes(n)
{
for(let i=0;i<prime.length;i++)
{
prime[i]=true;
}
for(let p = 2; p * p <= n; p++)
{
if (prime[p] == true)
{
for(let i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to find number of Sets
function NumberofSets(N)
{
SieveOfEratosthenes(N);
// Handle Base Case
if (N == 2)
{
document.write(1);
}
else if (N == 3)
{
document.write(2);
}
else
{
// Set which contains less
// than or equal to N/2
let ans = 1;
// Number greater than N/2 and
// are prime increment it by 1
for(let i = Math.floor(N / 2) + 1; i <= N; i++)
{
// If the number is prime
// Increment answer by 1
if (prime[i])
{
ans += 1;
}
}
document.write(ans);
}
}
// Driver Code
// Input
let N = 9;
// Function Call
NumberofSets(N);
// This code is contributed by unknown2108
</script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(K)