[C언어 기출문제&풀이] 친구 수

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

출처:www.dovelet.com

풀이 : 약수 활용 

소스코드 

#include <stdio.h>

int main()

{

 int n,i,j,asum=0,bsum=0,temp;

 scanf("%d",&n);

 for(i=1;i<=n;i++)

 {

  for(j=2;j*j<i;j++)

   if( i%j==0) asum+=j+i/j;

  if(j*j==i) asum+=j;

  asum++;

  for(j=2;j*j<asum;j++)

   if(asum%j==0) bsum+=j+asum/j;

  if(j*j==asum) bsum+=j;

  bsum++;

  if(bsum==i) printf("%d %d\n",i,asum);

 }

}