Zählen Sie die Anzahl der richtigen Fraktionen

Question

Ein Bruchteil p/q (p und q sind positive ganze Zahlen) ist richtig, wenn p/q < 1. Gegeben 3 < = N < = 50 000 000, schreiben Sie ein Programm, um die Anzahl zu zählen richtige Fraktionen p/q, so dass p + q = n, und p, q sind relative Primzahlen (ihr größter gemeinsamer Teiler ist 1). Dies ist mein 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); 
} 

Ich frage mich, ob ich es richtig gemacht. Gibt es trotzdem eine Beschleunigung des Algorithmus? Es dauerte meinen Laptop (i7-4700mq) 2,97 Sekunden mit Release-Modus, wenn N = 50 000 000.

Vielen Dank laufen.

Answer 1

Die wichtige Tatsache ist, dass wenn p + q = n und gcd(p, q) = k dann k n teilen müssen. Umgekehrt, wenn p ist Cofrime zu n dann q = n - p muss cofrime zu p sein.

Daher ist das Problem des Zählens coprime Paaren (p, q), die Summe n reduziert effektiv die Zahlen zu zählen, die teilerfremd zu n (Euler's totient, aka phi) und Dividieren dieser Zählung durch 2.

Es ist viel Code für die Berechnung der totient einer Zahl da draußen auf dem Netz, wie in der GeeksForGeeks Artikel Euler's Totient Function. Es läuft im Wesentlichen darauf hinaus, die Nummer zu faktorisieren, die ziemlich viel schneller sein sollte als Ihr aktueller Algorithmus (etwa 5 Größenordnungen). Habe Spaß!