친구수 문제

프로그램 명: amicable

제한시간: 1 초

어떤수 A 의 약수(단, 자신은 제외)의 합을 B 라 할 때

• A 와 B 가 같으면 완전수
• B 의 약수(자신은 제외)의 합이 다시 A 가 되는 경우를 친구수라 함.

친구수가 되는 최초의 수는 220 이다.

• 220 의 약수는 1,2,4,5,10,11,20,22,44,55,110,220 이 중 자신을 제외한 약수의 합은

  1+2+4+...+110 = 284

• 284 의 약수는 1,2,4,71,142,284 자신을 제외한 약수의 합은

  1+2+4+71+142 = 220

그러므로 220 과 284 는 친구수 이다.

입력

자연수 n ( n <= 10000 ) 을 입력으로 받아 이 수 까지의 친구수를 모두 출력하는 프로그램을 작성하는 것이 문제이다.

출력

두 수가 친구 수이면 두 수중 작은수를 먼저 출력한다. 또한 친구수가 여러개 존재하면 작은 수 기준 오름차순으로 한 줄에 한 쌍씩 출력한다.

입출력 예

입력

300

출력

220 284

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <iostream> #include <math.h>   #define MAX 10000   using namespace std;   int visit[10001];   int getSum(int num) // 약수의 합을 구하는 함수 {     if(num > MAX) return -1;       visit[num]=1;       int sum=1;     int endNum = sqrt(double(num));          for(int i=2; i<=endNum; i++){         if(num % i == 0){             sum += i;             if(i != endNum)                 sum += num / i;         }     }          return sum; }   int main() {     int n;          cin >> n;       for(int i=1; i<=n; i++){         if(visit[i]) continue;         int left = getSum(i); // i 의 약수의 합을 구함 left로 치환         int right = getSum(left); // left의 약수의 합을 구함         if(right==i){              if(left != i) cout << i << ' ' << left << endl; // 서로 대응되면 출력         }     } }