우선 가우스 정수는 아래와 같이 정의됩니다.


Definition. (Gaussian Integer)
두 정수 a, b에 대하여, 복소수 a + bi를 가우스 정수라고 한다.
Definition. (Divisibility)
두 가우스 정수 z, w에 대하여, w가 0이 아니고 z/w가 가우스 정수이면 z는 w로 나누어 떨어진다고 한다.


가우스 정수는 유클리드 정역입니다.


제가 하고 싶은 건 두 가우스 정수 z, w(!=0)을 입력받아 z가 w로 나누어 떨어지는지 확인하는 코드를 짜고 싶었습니다. 우선, 효율보다는 확실한 해답을 하나 찾아봤습니다. python으로 구현했는데 필요없는 부분은 생략하고 아이디어를 적자면 다음과 같습니다.

class GaussInt:
    def __init__(self, real, imag):
        self.real = real; self.imag = imag

    def real(self):
        return self.real
    def imag(self):
        return self.imag

    def __add__(self, r): 
        return sum of self and r(int or GaussInt)

    def __mul__(self, r):
        return product of self and r(int or GaussInt)

    def __abs__(self):
        return Taxi norm of self i.e. abs(self.real()) + abs(self.imag())

    def IsDivisibleBy(self, r):
        M = abs(self)
        for C s.t. abs(C) <= M:
            if self = C * r: return True
        return False

다만 당연히 모든 경우의 수를 체크하고, 그 때마다 곱셈 계산하고 비교하고 하다보니 느립니다. 조금 더 효율을 높일 수 있는 방법이 있을까요?