정보처리기능사 실기 요점정리#4 - 최대공약수 최소공배수 알고리즘

You are perfect! and this is TRUE!

정보처리기능사 실기 요점정리#4 - 최대공약수 최소공배수 알고리즘

- 정보처리기능사 실기 기출유형정리 및 요점정리 네번째는 배수 약수에 관련된 것들을 정리해봅니다.

1. 최대공약수 최소공배수 구하기

최대 공약수 구하는 알고리즘

- 두수를 입력받는다.

- 큰수를 작은수로 나눈다.

- 나누어 떨어지면 작은수가 바로 최대 공약수가 된다.

- 나누어 떨어지지 않으면 작은수를 큰수로 놓고 2번에서 구한 나머지로 나눠준다.

- 나누어 떨어지면 작은수가 최대 공약수가 된다.

- 나누어 떨어지지 않으면 작은수를 큰수로 놓고 4번에서 구한 나머지로 나눠준다.

...

- 이 과정을 반복한다.  

최소 공배수 구하는 알고리즘

- 원본자료 두수를 곱한뒤 위에서 구한 최대 공약수로 나눠준다.

20 17을 예로들면

20 / 17 = 1...3

17 /  3 = 5...2

엌ㅋㅋㅋㅋㅋㅋ최소공약수가 없음ㅋㅋㅋㅋ아나 꼭 예를 들어도 소수 17을...

이렇게 되면 최소공배수는 그냥 두 수를 곱한거ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

2. 약수 구하기

- N의 약수 = N을 나누면 나누어 떨어지게 만드는 수.

- 약수구하는 알고리즘은 어떤수를 입력받고 제수(나누는 수)를 1부터 입력받은 수까지 1씩 증가시키면 다 나눠서 나머지가 0 인것만 골라서 캐치하면 됨.

* 나머지가 0인지 알아보는 방법?

1) MOD 함수 이용하기.

2) 입력받은 수 - 제수x몫해서 나머지를 직접 구하기

약수 구하는 알고리즘

- 500을 입력받음

- 500/1 => 나머지 0이네? 1는 약수

- 500/2 => 나머지 0이네? 2는 약수

- 500/3 => 나머지 0 아니네? 노약수

...

- 500/500 => 나머지 0이네? 500은 약수

3. 배수 구하기

- N의 배수 = N으로 나누면 나누어 떨어지는 수

- 배수구하는 방법은 값을 1부터 목표수가까지 증가시키면서 8로 계속 나눠서

나머지가 0인것만 캐치하면 된다.

- 1~1000 사이의 8의 배수의 개수는?

- 1/8 = 나머지가 없엉 8의배수 아니네.

- 2/8 = 나머지가 없엉 8의배수 아니네.

...

- 726/8 = 90...나머지가 있네? 8의 배수 아니네

- 727/8 = 90...나머지가 있네? 8의 배수 아니네

- 728 = 91 나머지가 없네! 8의 배수!! [개수+1]

...

4. 완전수 구하기

- 완전수란 자신을 제외한 자신의 모든약수를 더했을때 자신이되는 기묘한 수를 말한다.

- 완전수 구하는 알고리즘 : 의외로 간단한데, 자신을 제외한 약수들을 구해서 모두 더한뒤 자신이 되는지 검사하고 되면 완전수 아니면 그냥 수. 자신을 제외한 약수구할때 나누는수를 1부터 ~ 자신/2 만큼으로 잡고하면 자신을 제외한 약수를 구할 수 있음.