정보처리기능사 실기#17 - 완전수 알고리즘, 완전수란 뭔가요?

음, 완전수에 관한건 처음보네. 정보처리기능사 실기 열일곱번째 유형은 완전수에 관한것인데요.

완전수가 무엇인지 알아본뒤 완전수 구하는 알고리즘을 알아봅니다.

My bonny pony lassie :3

정보처리기능사 실기시험 요점정리#17 - 완전수 그리고 완전수 알고리즘

1. 완전수란?

- 완전수는 자신을 제외한 자신의 약수를 더하면 자신이 나오는 기묘한 숫자.

- 완전수 예를 들면, 6이 있는데 6의 약수는 6 3 2 1 인데 자신을 제외하면 3 2 1 이를 모두 더하면 6.

2. 완전수 알고리즘의 핵심

- 자신을 제외한 약수를 구해야한다.

- 약수는 대상수를 어떤수로 나눴을때 나머지가 0일때 나눈 수가 약수가 된다.

- 이를 식으로 표현하면 N mod X = 0 이면 나누어 떨어지므로 X는 N의 약수

-  또는 R = N - (N/X) x X 일떄 R = 0 이면 나누어 떨어지므로 X는 N의 약수

- 그리고 구한 약수들을 더한 합값이 대상수와 동일하면 대상수는 완전수다.

* 그러고보니 그런... 약수의 성질???

- N의 약수는 N/2보다 같거나 작다.

- 고로 약수를 구할때 대상수N(나눠지는 목표수)/2 해주고 이것을 나머지가 0인지 구분하는 루프를 돌릴때

루프아웃 포인트로 하면 자기자신을 약수로 구하지도않으면서 불필요한 연산과정을 줄일 수 있게 된다. 

완전수 구하는 알고리즘 예제

1 ~ 1000 까지의 자연수중 완전수를 구해서 모두 더해서 출력하는 알고리즘은?

N : 1~1000이 될 대상수 변수

J : 나누는수 변수, 약수변수

R : 나머지 변수

SUM : 약수 합

SSUM : 완전수 합

STARTING POINT1

N = N + 1

J = 0

STARTING POINT2

J = J + 1

R = N - (N/J) x J //나머지 구하기

R = 0 이면 SUM = SUM + J //약수니까 더해줌

N/2 > J 이면 STARTING POINT2 아니면 OUT POINT1로 // N/2을 루핑 통제변수로 정함으로써 불필요한

연산을 제외하는동시에 자기자신은 약수에서 제외됨!

OUT POINT1

N = SUM 이면 이하 진행 아니면 STARTING POINT2로 가서 반복

SSUM = SSUM + N

N = 1000 이면 OUT POINT2로 아니면 STARTING POINT1로 가서 반복

OUT POINT2

출력::SSUM