# 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.

## Recent Comments