计算真分数的个数

Question

如果p/q < 1，则分数p/q（p 和q 是正整数）是适当的。给定 3 <= N <= 50 000 000，编写一个程序来计算真分数 p/q 使得 p + q = n，并且 p, q 是相对质数（它们的最大公约数是 1）。这是我的代码

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);
}

我想知道我是否做对了。反正有加速算法吗？当 N = 50 000 000 时，我的笔记本电脑 (i7-4700mq) 花了 2.97 秒运行释放模式。

非常感谢。

Answer 1

关键事实是如果p + q = n和gcd(p, q) = k那么k必须整除n。相反，如果 p 与 n 互质，则 q = n - p 必须与 p 互质。

因此，计算和为 n 的互质数对 (p, q) 的问题有效地简化为计算与 n 互质的数 (Euler's totient, a.k.a. phi) 并将其相除以 2 计数。

网上有大量用于计算数字总和的代码，例如 GeeksForGeeks 文章 Euler's Totient Function。它本质上归结为分解数字，这应该比您当前的算法快很多（大约 5 个数量级）。玩得开心！

计算真分数的个数

Count the number of proper fractions

primes

fractions

greatest-common-divisor