Compter le nombre de fractions correctes

Question

Une fraction p/q (p et q sont des entiers positifs) est correcte si p/q < 1. Étant donné 3 < = N < = 50 000 000, écrire un programme pour compter le nombre de les fractions propres p/q telles que p + q = n, et p, q sont des nombres premiers relatifs (leur plus grand commun diviseur est 1). Ce est mon 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); 
} 

Je me demande si je l'ai fait correctement. Est-il possible d'accélérer l'algorithme? Il a fallu 2,97 secondes à mon portable (i7-4700mq) pour fonctionner avec le mode Release lorsque N = 50 000 000.

Merci beaucoup.

Answer 1

Le fait essentiel est que si p + q = n et gcd(p, q) = k alors k doit diviser n. Inversement, si p est coprime à n, q = n - p doit être coprime à p.

où le problème du comptage de paires de premiers entre eux (p, q) cette somme à n réduit efficacement à compter les nombres qui sont premiers entre eux de n (Euler's totient, aka phi) et en divisant ce nombre par 2.

Il y a beaucoup de code pour calculer le nombre d'un nombre sur le net, comme dans l'article GeeksForGeeks Euler's Totient Function. Cela revient essentiellement à factoriser le nombre, ce qui devrait être un peu plus rapide que votre algorithme actuel (environ 5 ordres de grandeur). S'amuser!