## Introduction

Data Structures play a vital role in developing our problem-solving skills to crack the interview rounds of product-based companies.

We must print the number of sets formed in an Equivalence relation from a range**[2, N]** using given operations.

Before heading towards the problem, certain words should be clear in your head for thinking it in that way.

**What do you understand by Equivalence Relation?**

An equivalence relation is Reflexive, Symmetric, and Transitive.

**Reflexive Property**

This property states that for every real number a, a=a.

**Symmetric Property**

This property states that for all real numbers a and b, if a=b, then b=a.

**Transitive Property**

This property states that for all real numbers a, b, and c, if a=b and b=c, then a=c.

**What do you mean by GCD of two numbers?**

The greatest common factor(GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each integer.

For example, GCD(4,8) is 4.

Let's move to our problem statement for more clarity.

Also see, __Euclid GCD Algorithm__

## Problem Statement

We will be provided with an integer 'N' as input where we have to choose integers(distinct) from the range **[2 to N]**, if their GCD is greater than '1', then insert them into the same set as long as we find such integers. The sets formed will follow the equivalence properties, which states that if x and y are in the same set and y and z are in the same set, then x and z should be in the same set.

**We have to print the count of the total sets formed.**

Let's clear this mess with the help of an example.

**Example 1:**

**Input:** N= 5

**Output:** 2

**Explanation:** Integers from the range [2, N] are {2,3,4,5}, Here GCD of 2,3 is '1', so they can't be the same set. GCD of 2,4 is '2', so they can be in the same set. GCD of 3,5 is '1', so they can be in the same set. **Hence the two sets formed will be {2,4} and {3,5}.**

**Example 2:**

**Input: **N=9

**Output:** 3

**Explanation**: Integers from range [2,N] are {2,3,4,5,6,7,8,9}. Here the GCD of integers {2,4,6,8} are 2 and the GCD of integers {3,6,9} are 3 and GCD of {5} and {7} is ‘1’. But as we know that sets are in equivalence relation. So, according to the transitivity property, integer '6' is common in both sets. Hence all the integers of both sets lie in one set. As the question says, a set should contain two more distinct integers whose GCD is greater than '1' but 5 and 7 have gcd as 1. Therefore they will be in different sets.

**The total sets will be: {2,3,4,6,8,9}, {5}, {7}.**

Now that we have understood the question let's move towards our approach and implementation.