최대 공약수 구하는 문제에 질문이 있습니다!
PrinceSs
2023.04.01
두개의 정수를 입력받아서 최대 공약수 구하는 프로그램인데요
#include stdio.h
void gcm(int i, int j);
int main(void)
{
int x, y;
printf(두개의 정수 입력: );
scanf(%d %d, &x, &y);
gcm(x, y);
return 0;
}
void gcm(int i, int j)
{
int a,b=1;
for(a=1;a=(ij ? i:j) ;a++)
{
if(i%a==0 && j%a==0) //최대 공약수 조건 검사
b*=a;
}
printf(GCM: %d \n, b);
}
전 이렇게 했는데요 아무래도 반복문이 이상해서요
숫자가 작으면 맞는 결과가 나오는데 커지면 자꾸 이상한 결과가 나오더라구요
답변 기다리겠습니다!
-
천사
ㅋㅋㅋ 감사합니다! 소인수분해를 응용해서 할려고 했어요;;ㅎㅎ
-
각티슈
b*=a;
이부분이 무엇인가요?
b=a 아닌가요?
6,12를 한다면
2 * 3 * 6이 되서
결과는 36이 나오는데...
아무래도 소인수분해를 응용해서 하시려했으시던것같은데 (곱셈을 쓴것을 보면)
그러려면 b에 있는 약수가 a에 있는지 체크해줘서
b=b*a/gcd(b,a)등으로 해야할것같애요
뭐 그런의도가 아니라 공약수중 최대를 구하는것이라면
b=a가 맞고요