[실기] 15. 약수와 완전수

in 정보처리기사 on 기사 실기 알고리즘


약수와 완전수


설명

  • 완전수
    • 자연수 중에서 자기 자신을 뺀 약수의 합이 자기 자신과 같은 수을 뜻함
    • 예) 28의 약수 1, 2, 4, 7 ,14 ,28 중 1+2+4+7+14 = 28


문제

  • 4부터 500까지의 자연수 중에서 완전수를 찾아 출력하고 그 개수를 구하는 알고리즘을 제시하라


문제공략

  • 임의 자연수의 약수를 구할 때 절반으로 나누어 보면 자기 자신을 제외한 약수를 구할 수 있다.
    • 임의의 수의 약수, 28의 약수 = {1, 2, 4, 7, 14, 28}
    • 예) 28/2 = 14, 1+2+4+7+14 = 28


C

#include <stdio.h>

int main()
{
	int TN = 0;
    for (int N=4; N<=400; N++) {
        int SUM = 0;
        int K = N/2;
        for (int J=1; J<=K; J++) {
            if (N % J == 0) {
                SUM += J;                    
            }	            
        }
        //외부 반복문을 통해 1부터 (N/2)의 합이 N이면 TN카운터 처리
        if (N == SUM) {
            printf("N= %d\n", TN);
            TN++;
        }
    }
    
    printf("%d\n", TN);
}


JAVA

class Main {
	public static void main (String[] args) {
	    
	    int TN = 0;
	    for (int N=4; N<=400; N++) {
	        int SUM = 0;
	        int K = N/2;
	        for (int J=1; J<=K; J++) {
                if (N % J == 0) {
                    SUM += J;                    
                }	            
	        }
            //외부 반복문을 통해 1부터 (N/2)의 합이 N이면 TN카운터 처리
	        if (N == SUM) {
	            System.out.println("N=" + N);
	            TN++;
	        }
	    }
        
        System.out.println(TN);
	}
}