여기서는 두 수의 공약수를 구하는 방법을 알아보겠습니다. 모든 공약수를 찾지는 않겠지만 공약수가 몇 개인지 계산할 것입니다. 두 숫자가 12와 24와 같으면 공약수는 1, 2, 3, 4, 6, 12입니다. 따라서 공약수가 6개이므로 답은 6입니다.
알고리즘
countCommonDivisor(a, b)
begin count := 0 gcd := gcd of a and b for i := 1 to square root of gcd, do if gcd is divisible by 0, then if gcd / i = i, then count := count + 1 else count := count + 2 enf if end if done return count end
예시
#include<iostream> #include<cmath> using namespace std; int gcd(int a, int b) { if (a == 0) return b; return gcd(b%a, a); } int countCommonDivisors(int a,int b) { int gcd_val = gcd(a, b); //get gcd of a and b int count = 0; for (int i=1; i<=sqrt(gcd_val); i++) { if (gcd_val%i==0) { // when'i' is factor of n if (gcd_val/i == i) //if two numbers are same count += 1; else count += 2; } } return count; } main() { int a = 12, b = 24; cout << "Total common divisors: " << countCommonDivisors(a, b); }
출력
The differences array: 6 5 10 1