Archetypical Example: Euclid's Method of Computing Greatest Common Divisors 超典型的ソースコードの見本～最大公約数を計算する、ユークリッドの互除法

C

2015-03-31 14:48

1. /* A little algorithmic adventure in math,
2. // Greatest common denominator/divisor.
3. //
4. // Note that this does not attempt to properly handle negative numbers
5. // beyond what strtoul() does.
6. // (When did strtoul() start "casting" negatives to positive?)
7. //
8. // If anyone hassles me about Intellectual Property on this,
9. // I'll hit them over the head with a copy of Euclid, and again with　a copy of Knuth.
10. // Joel Rees, Amagasaki, March 2015
11. */
12. #include <stdio.h>
13. #include <stdlib.h>
14. long gcd( long numA, long numB )
15. {
16. long temp;
17. while ( numA != numB )
18. {
19. if ( numA < numB )
20. {
21. temp = numA;
22. numA = numB;
23. numB = temp;
24. }
25. numA -= numB;
26. }
27. return numA;
28. }
29. int main( int argc, char * argv[] )
30. {
31. long n1, n2;
32. char * parseP;
33. long divisor;
34. if ( argc != 3 )
35. { printf( "usage: %s <numA> <numB>\n",
36. argv[ 0 ] );
37. puts( "\tto calculate the greatest common divisor\n\tof two unsigned numbers." );
38. return EXIT_FAILURE;
39. }
40. n1 = strtoul( argv[ 1 ], &parseP, 0 );
41. if ( parseP > argv[ 1 ] )
42. {
43. n2 = strtoul( argv[ 2 ], &parseP, 0 );
44. if ( parseP > argv[ 2 ] )
45. {
46. divisor = gcd( n1, n2 );
47. printf( "greatest common divisor: %ld\n", divisor );
48. printf( "%ld/%ld => %ld/%ld\n", n1, n2, n1 / divisor, n2 / divisor );
49. return EXIT_SUCCESS;
50. }
51. else
52. {
53. printf( "%s is not an unsigned number I can recognize.\n", argv[ 2 ] );
54. }
55. }
56. else
57. {
58. printf( "%s is not an unsigned number I can recognize.\n", argv[ 1 ] );
59. }
60. return EXIT_FAILURE;
61. }