Given an integer N, repeatedly choose two distinct integers from the range 2 to N and if their GCD is found to be greater than 1, insert them into the same set, as long as possible. The sets formed in Equivalence Relation. Therefore, if integers a and b are in the same set and integers b and c are in the same set, then integers a and c are also said to be in the same group. The task is to find the total number of such sets that can be formed.
Examples:
Input: N = 3
Output: 2
Explanation: Sets formed are: {2}, {3}. They cannot be put in the same set because there GCD is 1.Input: N = 9
Output : 3
Sets formed are : {2, 3, 4, 6, 8, 9}, {5}, {7}
As {2, 4, 6, 8} lies in same set and {3, 6, 9} also lies in same set. Hence, all these lie in one set together, because 6 is the common element in both the sets.
Approach: The idea to solve the problem is based on the following observation that all the numbers less than or equal to N/2 belong to the same set because if 2 is multiplied in them, they will be even number and has GCD greater than 1 with 2. So the remaining sets are formed by numbers greater than N/2 and are prime because if they are not prime then there is a number less than or equal to N/2 which is the divisor of that number. The prime numbers from 2 to N can be found using the Sieve of Eratosthenes.
Below is the implementation of the above approach:
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 Nvoid 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 Setsvoid 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 Codeint main(){ // Input int N = 9; // Function Call NumberofSets(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static boolean prime[] = new boolean[100001];// Sieve of Eratosthenes to find// primes less than or equal to Nstatic 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 Setsstatic 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 Codepublic 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 approachprime = [True] * 100001# Sieve of Eratosthenes to find# primes less than or equal to Ndef 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 Setsdef 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 Codeif __name__ == '__main__': # Input N = 9 # Function Call NumberofSets(N)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{static bool []prime = new bool[100001];// Sieve of Eratosthenes to find// primes less than or equal to Nstatic 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 Setsstatic 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 Codepublic 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 approachlet prime = new Array(100001);// Sieve of Eratosthenes to find// primes less than or equal to Nfunction 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 Setsfunction 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// Inputlet N = 9;// Function CallNumberofSets(N);// This code is contributed by unknown2108</script> |
3
Time Complexity: O(N)
Auxiliary Space: O(K)
