最大公约数算法(gcd)

[huangblue]

Problem: Find the greatest common divisor of two nonnegative integers u and v. Step 1: If v equals 0, then you are done and the gcd is equal to u. Step 2: Calculate temp = u % v, u = v, v = temp, and go back to step 1.

[huangblue]

/ Function to find the greatest common divisor of two nonnegative integer values and to return the result /

include

int gcd (int u, int v) { 　 int temp; 　 while ( v != 0 ) { 　　 temp = u % v; 　　 u = v; 　　 v = temp; 　 } 　 return u; } int main (void) { 　int result; 　 result = gcd (150, 35); 　 printf ("The gcd of 150 and 35 is %i\n", result); 　 result = gcd (1026, 405); 　 printf ("The gcd of 1026 and 405 is %i\n", result); 　 printf ("The gcd of 83 and 240 is %i\n", gcd (83, 240)); 　return 0; }

[huangblue]

/ Function to find the greatest common divisor of two nonnegative integer values and to return the result /

include

int gcd (int u, int v) { int temp; while ( v != 0 ) { temp = u % v; u = v; v = temp; } return u; } int main (void) { int result; result = gcd (150, 35); printf ("The gcd of 150 and 35 is %i\n", result); result = gcd (1026, 405); printf ("The gcd of 1026 and 405 is %i\n", result); printf ("The gcd of 83 and 240 is %i\n", gcd (83, 240)); return 0; }

[huangblue]

The gcd of 150 and 35 is 5 The gcd of 1026 and 405 is 27 The gcd of 83 and 240 is 1

Process returned 0 (0x0) execution time : 0.016 s Press any key to continue.