[알고리즘] 서로소

서로소는 최대공약수가 1인 숫자들이다.

 

이 블로그 초반에 최대공약수와 최소공배수에 대한 개념을 정리한 적이 있다. 그것을 활용해보자.

 

int GCD(int a, int b) {
	int i;
	if (a > b)
		i = a;
	else
		i = b;

	for (int j = i; ;j--) {
		if (a % j == 0 && b % j == 0)
			return j;
	}
}

 

최대공약수에 대한 알고리즘이다. 자 그럼 최대공약수가 1이면 되니까 조건문을 사용하면 간단하겠다.

 

 

int GCD(int a, int b) {
	int i;
	if (a > b)
		i = a;
	else
		i = b;

	for (int j = i; ;j--) {
		if (a % j == 0 && b % j == 0)
			return j;
	}
}

void RelativelyPrime(int a, int b) {
	if (GCD(a,b) == 1) {
		printf("서로소 입니다!");
	}
	else {
		printf("서로소가 아닙니다!");
	}
}

int main() {
	RelativelyPrime(12, 4);
}

 

간단하게 프로그래밍 할 수 있다.