c언어 두수의 공약수 나열하기 최대공약수 구하기

  저번 포스팅에서는 한 수의 약수를 나열하는 것을 배워 봤습니다. 그를 응용해서 오늘은 두 수의 공약수를 구하는 프로그램과 최대공약수 구하는 프로그램을 한번 짜 보도록 하겠습니다.

  일단 소스코드를 보겠습니다. 정수형 변수 i 와 a, b를 선언합니다. 그 다음에 입력을 하는 것이죠. 가장 중요한 부분은 바로 for문과  if문이 아닐 까 싶습니다. for문에서 i는 1까지부터 i는 a와  b모두 같거나 작게 만들어 줍니다. 이때 if문을 써서 a나누기 i가 0이고 b나누기 i가 0이면 그 i값을 인쇄를 하는것이죠.

  24와 36을 예로 들어 보겠습니다. 24와보다 작은 수와 36보다 작은 수 둘다 작은 수니 24보다 작은 수겠죠. 거기에서 24와 36은 1로 나누어지니 1을 하고 2로 나누어지니 2를하고 이런식으로 쭉쭉쭉 나열하는것입니다.

  이번엔 두 수의 최대공약수를 한번 구해 보도록 하겠습니다. 일단 재귀 호출이라는 것을 알아야 하는데요. 점화식을 이용한 재귀호출을 사용하면 아주 간단하게 할 수 있습니다. 최대공약수는 점화식을 어떻게 구할까요. a와 0의 최대공약수는 당연히 a이니까 b=0일때는 a가 나옵니다. 그리고 b가 양수일때는 gcd(b,a%b)인데요. 24 36이라면 24와 36을 나눈 나머지는 12겠죠. 12와 36의 최대공약수를 구하는 겁니다. 컴퓨터가 멍청해서 바로 못구하고 이렇게 유클리드 호제법같은 것을 이용해야 하기 때문이죠. 12는 36으로 나누어 떨어지지만 24는 36으로 나누어 떨어지지 않기 때문에 저런 알고리즘을 써야 합니다.

  알고리즘을 짯다면 뭐 소스코드 짜는 것은 어렵지 않죠. 일단 gcd함수를 호출합니다. 그 다음에 b가 0이면 a를 호출하고 그렇지 않으면 b와 a나누기 b의 최대공약수를 리턴해줍니다. 원래 그리고 소스코드 짜는 방법은 int  main쪽부터 짜고 위로 올라가는 것입니다. 일단 x와 y를 선언해서 gcd함수를 프린트해야되는데 gcd함수를 불러 와야되겠죠. 이런 식으로 하면 됩니다.

  일단 알고리즘이라는 것을 아는 것이 가장 중요하다고 볼 수 있습니다. 컴퓨터는 하나하나 논리적으로 가지 않으면 프로그래밍자체가 불가능합니다. 그러니 하나하나따져서 보는 것이 가장 중요하다고 할 수 있죠. 알고리즘을 이해하는 것이 프로그래밍을 하는데 가장 기초가 되지 않나 싶습니다. 저도 초보자이지만 블로그를 꾸미면서 조금씩 알아가는 재미를 느끼고 있죠. 그럼 열심히 프로그램짜세요.^^*