Algorithm
Problem link- https://www.spoj.com/problems/IITKWPCB/
IITKWPCB - Check the coprimeness
Find largest non-negative number less than or equal to floor (N/2) which is coprime to N.
Two number a and b are considered to coprime if gcd (a, b) = 1.
Input
T : number of test cases (T <= 1000)
For next T lines, every line contains n >= 1 && n <= 10^12;
Output
For each test case, output as described in the problem statement.
Example
Input: 4
3
4
5
100
Output: 1
1
2
49
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
def gcd(a, b):
while a > 0 and b > 0:
if a >= b:
a %= b
else:
b %= a
return a + b
T = int(input())
for _ in range(T):
N = int(input())
for i in range(N // 2, 0, -1):
if gcd(N, i) == 1:
print(i)
breakInput
4
3
4
5
100
3
4
5
100
Output
1
1
2
49
1
2
49
#2 Code Example with C++ Programming
Code -
C++ Programming
#include<bits/stdc++.h>
using namespace std;
#define pi 3.14159265358979323846264338327950
const int N=1e6+20,mod=(int)(1e9)+7;
#define ONLINE_JUDEGE
#define pb push_back
#define ull unsigned long long
#define ll long long
int main(){
#ifdef ONLINE_JUDEGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int T;
scanf("%d",&T);
while(T--){
ll num;
cin>>num;
ll ans=(ll)floor(num/2);
if(num%2)
cout<<ans-1<<endl;
else
cout<<ans<<endl;
}
return(0);
} Input
4
3
4
5
100
3
4
5
100
Output
1
1
2
49
1
2
49
Demonstration
SPOJ Solution-Check the coprimeness-Solution in C, C++, Java, Python