NAJPWG - Playing with GCD
Tanmoy recently learn about Euclid gcd algorithm. This algorithm looks like:
gcd(a, b): if (b == 0): return a return gcd(b, a % b)
Now he want to find out how many pair (x, y) can be possible in range N, which gcd is greater than 1. Here pair (x, y) and (y, x) consider as same pair. 1<=x, y<=N.
He can find out it small number easily but for a large number its really hard to find out. Now he needs your help. Write a programme that find out number of such pair.
Input
Input start with an integer number T ( ≤ 10^5), which is number of test cases.
Each test case contain a integer N (1 ≤ N ≤ 10^5).
Output
For each case, print case number and desired answer
Sample
Input: 2 3 4 Output: Case 1: 2 Case 2: 4
hide comments
mahilewets:
2017-09-07 16:31:10
I think answer(3)=2 because gcd(2,2)=2>1 and gcd(3,3)=3>1
|
|
azam_9:
2016-06-22 20:03:31
Beware of output format..costed me many W.A.. |
|
Piyush Kumar:
2016-06-21 16:53:55
@atuldo, It is not mentioned that x and y cannot be equal. So for N=3, (2,2) and (3,3) are pairs whose gcd is greater than 1.
|
|
atuldo:
2016-06-19 13:57:25
for N= 3 there are no pairs where gcd is greater than 1 |
|
Siddharth Singh:
2016-06-18 09:52:07
Practising On HackerEarth Surely Helped <3
|
|
Rashi Gehani:
2015-05-31 23:18:02
My 100th :-) |
|
Gaurav sharma:
2015-02-19 14:54:04
use long long.......int cost me 1 WA :( |
|
Anubhav Gupta:
2015-01-28 11:31:06
Take care of the output format, costed me 4 WA :/ |
Added by: | Najmuzzaman |
Date: | 2014-10-31 |
Time limit: | 0.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |