Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1120
A fraction m n is basic if 0 ≤ m < n and it is irreducible if gcd(m, n) = 1. Given a positive integer n, in this problem you are required to find out the number of irreducible basic fractions with denominator n. For example, the set of all basic fractions with denominator 12, before reduction to lowest terms, is 0 12 , 1 12 , 2 12 , 3 12 , 4 12 , 5 12 , 6 12 , 7 12 , 8 12 , 9 12 , 10 12 , 11 12 Reduction yields 0 12 , 1 12 , 1 6 , 1 4 , 1 3 , 5 12 , 1 2 , 7 12 , 2 3 , 3 4 , 5 6 , 11 12 Hence there are only the following 4 irreducible basic fractions with denominator 12 0 12 , 5 12 , 7 12 , 11 12 Input Each line of the input contains a positive integer n (< 1000000000) and the input terminates with a value 0 for n (do not process this terminating value). Output For each n in the input print a line containing the number of irreducible basic fractions with denominator n.
Sample Input 12 123456 7654321 0
Sample Output 4 41088 7251444
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
#define N 40000 // larger than sqrt of 1e9
vector<int> primes;
void sieve(){
primes.clear();
bitset < N> isPrime;
isPrime.set();
isPrime[0] = isPrime[1] = false;
for(long long i=2;i i+It N;i++){
if(isPrime[i]) {
primes.push_back(i);
for(long long j=i*i;j i+It N;j+=i)
isPrime[j] = false;
}
}
}
// Eulter's Phi (Totient) function
// number of positive integers coprime to n, gcd(x,n) = 1
// basic idea of euler's phi is to remove fraction that is a factor of the prime
// N * mul(1-1/PF) for all PF
int eulerPhi(int n) {
int ans = n; // itself
for(int idx=0;primes[idx]*primes[idx] <= n; idx++) {
if (n % primes[idx] == 0) ans -= ans/primes[idx];
while(n % primes[idx] == 0) {
n /= primes[idx];
}
}
if (n != 1) ans -= ans/n;
return ans;
}
int main()
{
sieve();
int n;
while(scanf("%d",&n),n) {
printf("%d\n", eulerPhi(n)>;
}
}Input
123456
7654321
0
Output
41088
7251444
Demonstration
UVA Online Judge solution - 10179 - Irreducable Basic Fractionss - UVA Online Judge solution in C,C++,Java!!