[알고리즘] 완전수(perfect number) 개념과 코드

🌟 완전수: 고대부터 사랑받아온 "완벽한 숫자"

📌 완전수란?

**완전수(perfect number)**는 자기 자신을 제외한 약수들의 합이 자기 자신과 똑같은 숫자를 말한다.

✅ 예시 1: 6

• 약수: 1, 2, 3, 6
• 자기 자신(6)을 제외한 약수: 1, 2, 3
• 합: 1 + 2 + 3 = 6 ✅ → 완전수!

✅ 예시 2: 28

• 약수: 1, 2, 4, 7, 14, 28
• 제외: 1 + 2 + 4 + 7 + 14 = 28 ✅ → 또 완전수!

이처럼 **“약수의 합 = 자기 자신”**이 되는 숫자가 바로 완전수다.

---

🏛️ 완전수의 역사: 수천 년 전부터 사랑받은 개념

완전수는 고대 그리스부터 연구되었고, 수학자 피타고라스 학파에서는 완전수를 숫자의 조화로 여겼어.
특히 고대인들은 완전수가 우주의 질서나 신성한 상징이라고까지 생각했어.

• 6은 첫 번째 완전수 → 6일간 창조, 7일째 쉬었다는 성경과도 연결
• 28은 두 번째 완전수 → 28일은 달의 주기와 관련

즉, 자연과 인간의 세계에도 수학적 완벽함이 존재한다는 관점으로 받아들였던 거야.

---

🧠 완전수의 수학적 구조

기본 개념은 간단하지만, 점점 더 큰 완전수를 찾는 건 굉장히 어렵고 신기한 일이야.
가장 놀라운 건 이거야:

모든 짝수 완전수는 특정한 공식을 따름

수학자 유클리드가 증명한 공식:

짝수 완전수 = 2^(p−1) × (2^p − 1)

여기서 (2^p − 1) 이 소수여야 해. 이런 소수를 **메르센 소수(Mersenne prime)**라고 해.

✅ 예: p = 2

• 2² − 1 = 3 (소수)
• 완전수 = 2^(2−1) × (2² − 1) = 2 × 3 = 6

✅ 예: p = 5

• 2⁵ − 1 = 31 (소수)
• 완전수 = 2⁴ × 31 = 16 × 31 = 496

이런 방식으로 만들어진 짝수 완전수는 지금까지 수천만 자리까지 발견되고 있어.

---

❓ 홀수 완전수는 존재할까?

놀랍게도, 아직까지 홀수 완전수는 단 하나도 발견되지 않았다.
그리고 수학자들은 수백 년간 이걸 찾으려 했지만… 지금도 **"홀수 완전수는 존재하지 않는다"**라는 미해결 문제로 남아 있어!

즉, 이건 아직 아무도 못 푼 수학 미스터리!

---

✨ 한 줄 요약

완전수는 단순한 숫자를 넘어서, 고대의 신화부터 현대 수학의 난제까지 이어지는 숫자 속 숨겨진 완벽함이다.

---

 
 

✅ 완전수 판별 의사코드 (Pseudocode)

Function isPerfect(n):
    sum ← 0
    For i from 1 to n - 1:
        If n mod i = 0:
            sum ← sum + i
    If sum = n:
        Return True
    Else:
        Return False

---

✅ 일정 범위 내 완전수 찾기

Function findPerfectNumbers(limit):
    perfectList ← empty list
    For n from 2 to limit:
        If isPerfect(n):
            Add n to perfectList
    Return perfectList

---

🔍 예제:

print(findPerfectNumbers(10000))
→ Output: [6, 28, 496, 8128]