취미 알고리즘 - 친밀 수
정수 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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.