#include <stdio.h> int num[10000]={0}; void set(int a); //내림차순으로 정렬 int max(int n, int m); //최대공약수를 구하는 함수 int min(int n, int m, int ax); //최소공배수를 구하는 함수 int main(void) { int n, m, aa, ax, am; scanf("%d %d", &n, &m); if(n>m) { aa=n; n=m; m=aa; } ax=max(n, m); am=min(n, m, ax); printf("%d\n%d", ax, am); return 0; } void set(int a) { int i, j, mm, temp; for(i=0; i<a && num[i]!=0; i++) { mm=i; for(j=i+1; j<=a && num[j]!=0; j++) { if(num[mm]<num[j]) mm=j; } if(i!=mm) { temp=num[i]; num[i]=num[mm]; num[mm]=temp; } } } int max(int n, int m) { int i, c=2; //n의 약수 num[0]=1; num[1]=n; for(i=2; i<=(n/2) && num[c-1]!=i; i++) { if(n%i==0) { num[c++]=i; if(i==(n/i)) break; num[c++]=n/i; } } c--; set(c); for(i=0; i<=c && num[i]!=0; i++) { //printf("[%d] %d\n", i, num[i]); if(m%num[i]==0) break; } return num[i]; } int min(int n, int m, int ax) { int i, ans=1; ans*=n; ans*=m/ax; return ans; }
2018.01.02 19:45
정올 - 실력키우기 - 최대공약수와 최소공배수(1658)
조회 수 1345 추천 수 0 댓글 0