취미 알고리즘 - 친밀 수

1114 단어 알고리즘Numbers
취미 알고리즘 - 친밀 수:
정수 a 의 인자 와 정수 b, 정수 b 의 인자 와 정수 a 와 같 으 면 a 와 b 는 친밀 수 이다.
1)  현재 수의 진 인 자 를 계산 하고 Sum 을 구하 고 얻 기;
2)  진짜 인자 의 합 에 대해 인자 와 FSum 을 재 구 합 니 다.
3)  FSum 이 원수 와 같 는 지 판단 하기;
#include <stdlib.h>
#include <stdio.h>

int IsFriendNum(int nNum)
{
    int i = 1;
    int nSum  = 0;
    int nFSum = 0;

    for (i = 1; i < nNum/2+1; i++)
    {
        if (nNum % i == 0)
        {
            nSum += i;
        }
    }

    for (i = 1; i < nSum/2+1; i++)
    {
        if (nSum % i == 0)
        {
            nFSum += i;
        }
    }

    if (nFSum == nNum)
    {
        printf("%d and %d are friend numbers
", nNum, nSum); } return 0; } int main() { int nRange = 100000; int i = 1; for (i=1; i < nRange; i++) { IsFriendNum(i); } scanf("%d", &i); return 0; }

알고리즘 복잡 도 분석: 1) 구 단 개수 x 의 인자 와 Sum 의 복잡 도 는 O (x) = x / 2 이다.2)  Sum 의 인자 와 FSum 의 복잡 도 는 O (x) = x / 2 이다.3)  이 두 부분의 총 시간 은 O (X) = X 이다.4)  데이터 의 범 위 는 n O (n) = 1 + 2 +... + n = n*(n-1)/2

좋은 웹페이지 즐겨찾기