# Divide first n natural number into minimum number of co-prime subsets

It is to divide the first n natural number into the minimum number of subsets such that each element is pairwise co-prime with every other element from the subset.

Let’s move towards the solution, subsets will have elements whose pairwise gcd is 1, i.e. no two elements will have a common factor, which implies, multiples of some number will be in different subsets. For example, multiple of 2 i.e. 2,4,6,8,10,….. each will be in different subsets, multiples of 3 i.e. 3,6,9,12…. will be in different subsets, etc. For any given n, the maximum number of multiples less than n will of multiples of 2. So, the minimum number of subsets, can be formed that contains pairwise co-prime numbers will be the number of multiples of 2 less than equal to n, that is (integer) n/2.

Now, forming each subset. As each adjacent pair of natural numbers is co-prime and each adjacent pair of odd numbers is co-prime, each odd number can be placed with its adjacent even number. 1 can be placed in any subset as it is co-prime with any other number.

Have a look for some value of n,

```For n=1, minimum number of subset is 1, subsets is {1}.
For n=2, minimum number of subset is 1, subsets is {1,2}.
For n=3, minimum number of subset is 1, subsets is {1,2,3}.
For n=4, minimum number of subset is 2, subsets is {1,2},{3,4}.
For n=5, minimum number of subset is 2, subsets is {1,2,5},{3,4}.
For n=6, minimum number of subset is 3, subsets is {1,2},{3,4},{5,6}.
For n=7, minimum number of subset is 3, subsets is {1,2,7},{3,4},{5,6}.
For n=8, minimum number of subset is 4, subsets is {1,2},{3,4},{5,6},{7,8}.
For n=9, minimum number of subset is 4, subsets is {1,2,9},{3,4},{5,6},{7,8}.```

C++ implementation is given below

```#include<bits/stdc++.h>
using namespace std;
int main()
{
long n,k;
cout<<"enter n:";
cin>>n;
if(n==1){
cout<<"minimum number of subset: "<<1<<endl;
cout<<"subsets: ";
cout<<"{1} "<<endl;
}else {
k=n/2;
cout<<"minimum number of subset: "<<k<<endl;
cout<<"subsets: ";
if (n & 1) {//if n is odd
cout<<"{1 2 "<<n<<"} "<<endl;
} else {//if n is even
cout<<"{1 2}"<<endl;
}
for (int i=3;i<n;i+=2) {
cout<<"{"<<i<<" " <<i+1<<"} "<< endl;
}
}
return 0;
}```

Donot hesitate to ping me in the comment section below.

Share on Social Media Mukuldeep Maiti

An unrecognized crazy being with random thoughts lost in unknown