適切な分数を数える

Question

p/q <の場合、分数p/q（pとqは正の整数）が適切です。3 < = N < = 50 000 000を指定すると、 p + q = nとなるような適切な分数p/qであり、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）は、N = 50 000 000のときにリリースモードで動作するのに2.97秒かかった。

ありがとう。

Answer 1

重要なことは、p + q = nとgcd(p, q) = kの場合、kはnを分けなければならないということです。逆に、pがnと共時ならば、q = n - pはpとの間にある必要があります。

したがって互いに素対（P、Q）への和N効果がある2

によってその数をN（Euler's totient、別名PHI）と互いに素である数をカウントし、分割に帰着をカウントする問題GeeksForGeeksの記事Euler's Totient Functionのように、ネット上の数字の合計を計算するコードがたくさんあります。本質的には、現在のアルゴリズム（約5桁の大きさ）よりもはるかに高速でなければならない数値を因数分解することにまで至ります。楽しむ！