모두의 코드 커뮤니티

C언어 오버플로 질문드립니다

unsigned형을 사용하며, 완전수,초과수,부족수 판별하는 코드입니다

#include <stdio.h>
unsigned f(unsigned n)
{
    unsigned i=1, sum = 0;
    do
    {
        {if (n % i == 0)
            sum += i; }
        i++;
    }
        while (i < n);

    return sum;
}

main()
{
    unsigned n;
    printf("2이상 4294967295이하의 자연수를 입력하시오:\n");
    scanf("%d", &n);

    if (n == f(n) )
        printf("%u 는 완전수.\n", n);
    else if (n > f(n) )
        printf("%u 는 부족수.\n", n);
    else if (n < f(n) )
        printf("%u는 초과수.\n", n);
}

4000000000이상의 수는 올바른 값이 제대로 출력이 안됩니다.
예를 들어 4000000000는 초과수인데 부족수로 뜨네요
이유가 sum+=i; 이 부분이 큰수일때 오버플로에 대한 대비가 없다고 하는데

질문1)unsigned형은 4294967295부터 오버플로 되는걸로 알고있는데, 왜 4000000000부터 오버플로되는건가요?

질문1-1)그렇다면 해결법은 else if 로 4000000000로 넘어가는 수를 따로 해줘야 하나요?
따로 해줘도 4000000000이상이므로 똑같이 오버플로되지않나요?

질문2) while(i<n); 이 부분이 큰수에 대하여 시간이 오래걸리는 비효율적인 프로그램으로 만든다는데
어떤식으로 변형해야되는건가요? while(1< n/i) , while(i/n<1) 요런식으로 해봤는데도 시간은 똑같이 오래걸리네요

1 Like

위 경우 n 이 오버플로우 된 것이 아니라 sum 이 오버플로우 된 것입니다. 따라서 sum 에는 제대로된 덧셈 결과가 들어갈 수 없겠지요.

해결법은 더 큰 자료형을 이용하거나 (uint64_t 를 쓰시면 됩니다), 큰 수를 다루는 라이브러리를 사용해야겠지요.

좀 더 효율적으로 짜기 위해서는 소인수 분해를 한 다음에 약수들의 합을 구하는 공식을 사용하면 되지 않을까요? 적으로 루트 N 까지만 하면 되니까요