[C/Python] 약수, 배수와 소수 1

1. 약수와 배수의 관계 (5086번)

두 수 A, B의 관계를 나머지 연산자(%)로 판별하는 가장 기초적인 단계입니다.

• 핵심 로직:
  • B % A == 0: A는 B의 약수(Factor)
  • A % B == 0: A는 B의 배수(Multiple)
• 💡 Key Point:
  • C++: while(cin >> a >> b && (a != 0 || b != 0))와 같은 입력 제어 숙달.
  • Python: sys.stdin을 이용한 빠른 여러 줄 입력 처리.

---

2. 약수 구하기와 완전수 (2501번, 9506번)

약수를 리스트에 담거나 개수를 세어 특정 조건을 만족하는지 확인합니다.

• 핵심 로직: 1부터 N까지 나누어 떨어지는 수를 탐색.
• 완전수(Perfect Number): 자신을 제외한 약수들의 합이 자신과 같은 수.
• 💡 Key Point:
  • C++: vector<int>와 push_back을 이용한 동적 저장 및 0-based 인덱스 주의.
  • Python: " + ".join(map(str, nlist))를 활용한 세련된 출력 포맷팅.

---

3. 소수 판별 알고리즘 (1978번, 2581번)

소수의 정의(1과 자기 자신만 약수로 가짐)를 코드로 구현합니다.

• 핵심 로직: 2부터 N-1까지 나누어 떨어지는 수가 있는지 확인.
• 성능 최적화: N까지 돌지 않고 **제곱근(sqrt{N})**까지만 확인해도 충분함!
• 💡 Key Point:
  • 공간 복잡도: 소수를 리스트에 다 담기보다, 변수(sum, min)만 사용하여 메모리 점유율을 O(1)로 유지하는 보안적/효율적 코딩 습관.

---

4. 소인수분해 (11653번)

어떤 수를 소수들의 곱으로 분해하는 과정입니다. 암호학(RSA)의 근간이 되는 원리입니다.

• 핵심 로직: 2부터 시작해 나누어떨어질 때까지 계속 나누고, 몫을 갱신.
• 최적화 공식:
• C++

   

  for (int i = 2; i * i <= n; i++) {
      while (n % i == 0) { cout << i << endl; n /= i; }
  }
  if (n > 1) cout << n; // 남은 소수 처리
  

• 💡 Key Point:
  • i * i <= n 조건을 통해 O(sqrt{N})의 빠른 속도로 1,000만 단위의 수도 처리 가능.

---

🏁 공부를 마치며 (Self-Feedback)

• 수학적 통찰: "약수의 개수는 N/2개 이하이다", "약수는 쌍으로 존재하므로 sqrt{N}까지만 조사하면 된다"는 원리를 코드로 녹여냄.
• 보안 전공자의 시선: C++의 size_t 언더플로우 위험성을 인지하고 (int) 캐스팅이나 조건식 변경(i + 1 < size)으로 안전한 코드를 작성함.
• 정보처리기사 대비: 2026년 4월 20일 시험에 단골로 나오는 '완전수 판별'과 '소수 루프 빈칸 채우기' 유형을 완벽히 이해함.