[Dovelet] 친구수/amicable

1. 문제

프로그램 명: 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

출처: http://211.229.66.5/index.php ☜' Dovelet'이란 알고리즘 트레이닝하기에 매우 좋은 사이트입니다.   

        위의 문제는 Dovelet의 4 계단의 '친구수/amicable' 문제입니다.

2. 내가 작성한 코드

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 #include <stdio.h>   int main (void) {     int input, sum1, sum2, i, j, k;     scanf("%d", &input);       for(j=1; j<=input; j++)     {         sum1 = sum2 = 1;         for(i = 2; i<j; i++)         {                         if(j % i == 0)                 sum1 += i;                         }                 for(k = 2; k < sum1; k++)         {                         if(sum1 % k == 0)                 sum2+=k;         }         if(sum2 == j)         {             if(sum1 == sum2)                 continue;             else if(sum1 < sum2)                      printf("%d %d\n", sum1 , sum2);                         }     }     return 0; }

더 쉽고 빠르게 결과를 출력할 수 있는 좋은 방법이 있다면 댓글로 공유 해주세요!