Divisor Friends :
Difficulty Level : Easy
Submissions : 318
Asked In :
Marks :10
: 4 | : 1
There are $$$N$$$ students in the class, and each student has a favorite number $$$F_i$$$ given in the form of the array $$$F$$$.
$$$A$$$ Student is a friend of another student $$$B$$$ if at least one of these two conditions are satisfied
- $$$gcd(A,B) > 1$$$
- $$$A$$$ and $$$B$$$ have a common friend, ie $$$A$$$ is friend of $$$C$$$ and $$$B$$$ is also friend of $$$C$$$
Find the minimum number of groups that can be formed such that in a group, a member is friend with all other members.
A student belongs to exactly one group.
The first line contains one integer $$$1 \le N \le 10^5$$$, denoting the number of students in the class.
The second line contain $$$N$$$ integers,$$$i^{th}$$$ denoting the favorite number of student $$$i$$$
Output the minimum number of groups that can be formed such that in a group, a member is friend with all other members.
4 2 4 6 5
2
4 2 6 3 21
1
