In a particular social network, friends are automatically allocated to users by the system, and users cannot add friends of their choice on their own. There are currently N users on the social network, labeled from 2 to N + 1.
For every user (where I ranges from 2 to N + 1), the system allocated all the users labeled with multiples of I as the user’s friends (if possible).
One day, all social network users come together for a meeting and form groups such that each person in a group is a direct friend or a friend or a friend of every other person of that group.
Find the total number of groups.
Input Specification:
input: N, denoting the number of users on the social network
Output Specification:
Your function should return the number of groups that can be formed on given conditions:
Example 1:
input1: 5
Output: 2
Explanation:
Two groups will be formed:
2, 3, 4, 6
5
Example 2:
input1: 10
Output: 3
Explanation:
Three groups will be formed:
2, 3, 4, 5, 6, 8, 9, 10
7
11