Little stuart and his teacher HackerEarth

general
, , , , , , ,
1

Little Stuart is a smart guy, and he loves mathematics. Today his math teacher taught his class about common factors. After finishing the class his teacher asked them a question: For a given number “n” calculate the number of unordered pairs (a,b) which have at least one common factor where 1 <= a < b <= n .

Note: 1 is not considered as common factor.

Input :
First line contain the number of test cases “t”
Next “t” lines contain a number “n”

Input Constraints:

1<=T<=100000

1<=n<=1000000

Output:
For each case print total number of pairs.
Sample Input
3
1
2
5

Sample output
0
0
1

Explanation
For testcase - 3 ,

N = 5

Some possible pairs = [(1, 2), (2, 3), (2, 4), (3, 4), (4, 5)]

The only pair which has common factor is (2, 4). So the answer is 1 for N = 5.

Note: 1 is not considered as common factor.
Time Limit 1 sec(s)
Memory Limit 256 MB
Source Limit 1024 KB

1 Like
2

@himeshkumar90 what you tried to solve this question ?

you can try brute force to generate output for small test case say for N=1 to 10

i appied brute force and outputs for N=1 to 10 are :

0, 0, 0, 1, 1, 4, 4, 7, 9, 14
search on OEIS and i found this link Series

And there is a formula for this series :

a(n)=n*(n-1)/2 + 1 - sum( phi(i), i=1…n)

Now i don’t think there is something else remaining in he question now you can solve this question.
Here is my AC solution Solution
Thanks !

2 Likes
3

Why don’t you try two dimintional array to get the paires,
That easy and should help?