str = str + '1';은 str + '1'을 계산하기 위해 str의 기존의 내용이 모두 복사되어 새로운 string이 만들어지고 그 뒤에 '1'을 추가한 뒤 str에 대입하는 과정이기 때문에 연산을 수행할 때마다 새로운 문자열의 길이에 비례하는 시간이 걸립니다. 1+2+...GCD(n,m)의 시간이 걸리므로 O(GCD(n,m)^2)의 시간이 걸립니다.

단순히 문자열 객체의 뒤에 문자를 덧붙이기 위해서는 = + 가 아니라 +=을 써야 합니다.

또한 현재 루프의 조건문 검사 방식도 다소 비효율적입니다. GCD(n,m)은 한 번만 계산하면 되는데, 이 코드에서는 조건문에 GCD(n,m)을 넣었기 때문에 루프를 돌 때마다 GCD(n,m)을 매번 계산하고 있습니다. 값은 미리 따로 구해서 변수에 저장해두고 조건문에서는 변수값으로 체크하는 편이 훨씬 효율적입니다.

감사합니다.. 많이 배우고 갑니당..!