Подсчитайте количество правильных дробей

Question

Фракция p/q (p и q - положительные целые числа) является правильной, если p/q < 1. Учитывая 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);
}

Интересно, правильно ли я это сделал. Есть ли способ ускорить алгоритм? Моему ноутбуку (i7-4700mq) потребовалось 2,97 секунды для запуска в режиме выпуска, когда N = 50 000 000.

Большое спасибо.

Answer 1

Ключевым фактом является то, что если p + q = n а также gcd(p, q) = k тогда k должно делить n. И наоборот, если p взаимно прост с n, то q = n - p должно быть взаимно с р.

Следовательно, проблема подсчета взаимно простых пар (p, q), которые суммируются с n, эффективно сводится к подсчету чисел, взаимно простых с n ( число Эйлера, aka phi) и делению этого числа на 2.

В сети есть много кода для вычисления коэффициента числа, например, в статье Toeent Function Эйлера в статье GeeksForGeeks. По сути, это сводится к факторизации числа, которое должно быть немного быстрее, чем ваш текущий алгоритм (около 5 порядков). Повеселись!