[코드트리 조별과제] 1주차 정리 (최대공약수 구하기/ 최소공배수 구하기/ 출력결과20)

CODING TEST/Code Tree

[코드트리 조별과제] 1주차 정리 (최대공약수 구하기/ 최소공배수 구하기/ 출력결과20)

더라 2024. 7. 21. 17:10

728x90

1주차는 시험이 있기도 하고,

오랜만에 코테를 공부하기 때문에

쉬엄쉬엄 가기고 했다.

감을 익히고자 기본기인

코드트리의

[프로그래밍 연습] - [함수] - [값을 반환하지 않는 함수]를 풀었다.

학습내용

최대공약수 구하기

[코드트리] 최대공약수 구하기

최대공약수는 공약수와 지수로 구하는 방법이 있다.

지수로 구하는 방법은 지수가 있는 형태로 바꾼 뒤 공통된 수 중

지수가 작은 것을 선택해서 곱하는 방법이다.

공약수로 구하는 방법은 소인수 분해를 이용한다.

소인수 분해시 큰 수를 사용하면 계산 횟수가 줄어든다.

큰 수를 사용한다는 점을 이용해서

코드를 작성할 수 있다.

def cal_gcd(n, m):
    for i in range(min(n,m),0,-1):
        if n % i == 0 and  m % i == 0:
            return i


n, m = map(int, input().split())
print(cal_gcd(n,m))

두 수 사이의 최대공약수는

최대 두 수 n, m중 작은 수가 될 수 있다.

3과 6의 경우 3이 공통된 약수지만

6은 3의 약수가 아니기 때문에 해당되지 않는다.

for i in range(min(n, m),0,-1)를 범위로

설정한다. 큰 수부터 계산하여 연산 횟수를 줄일 수 있다.

두 수를 공약수 후보로 나누었을 때

나머지가 공통으로 0으로 떨어질 경우

그 수가 두 수의 최대 공약수다.

728x90

최소공배수 구하기

[코드트리] 최소공배수 구하기

def lcm(n,m):
    for i in range(max(n, m), (n*m)+1):
        if i%n==0 and i%m==0:
            return i

n,m = map(int, input().split())
print(lcm(n,m))

두 수중 큰 수는

최소 공배수의 후보가 될 수 있다.

그리고 두 수를 곱하여 나온 결과는

공배수가 된다.

이를 이용해

for i in range(max(n, m), (n*m)+1)

범위를 설정한다.

공배수 후보를 각 수로 나누었을 때

나머지가 공통으로 0으로 떨어질 경우

그 수가 두 수의 최소 공배수다.