Count the number of proper fractions

Question

A fraction p/q (p and q are positive integers) is proper if p/q < 1. Given 3 <= N <= 50 000 000, write a program to count the number of proper fractions p/q such that p + q = n, and p, q are relative primes (their greatest common divisor is 1). This is my code

bool prime_pairs(int x, int y) {
    int t = 0;
    while (y != 0) {
        t = y;
        y = x % y;
        x = t;
    }
    return (x == 1);
}

void proer_fractions(int n) {
    int num = n % 2 == 0 ? n / 2 - 1 : n / 2, den = 0, count = 0;
    for (; num > 0; --num) {
        den = n - num;
        if (prime_pairs(num, den))
            ++count;
    }
    printf("%d", count);
}

I wonder if I did it correctly. Is there anyway to speed up the algorithm? It took my laptop (i7-4700mq) 2.97 seconds to run with Release mode when N = 50 000 000.

Thank you very much.

Answer 1

The key fact is that if p + q = n and gcd(p, q) = k then k must divide n. Conversely, if p is coprime to n then q = n - p must be coprime to to p.

Hence the problem of counting coprime pairs (p, q) that sum to n effectively reduces to counting the numbers that are coprime to n (Euler's totient, a.k.a. phi) and dividing that count by 2.

There is plenty of code for computing the totient of a number out there on the 'net, like in the GeeksForGeeks article Euler's Totient Function. It essentially boils down to factoring the number, which should be quite a bit faster than your current algorithm (about 5 orders of magnitude). Have fun!