프로젝트 오일러 # 23에 대한 내 코드의 최적화

Question

프로젝트 오일러의 Problem no 23을 풀고 있습니다. 나는 간단한 논리를 사용했지만 정확한 답을 얻고 있지만 프로그램을 실행하는 데는 상당한 시간이 걸린다.

내 코드를 최적화 할 수있는 방법이 있습니까?

먼저 두 개의 풍부한 숫자의 합계 인 모든 숫자를 계산 한 다음 전체 합에서 뺍니다.

int factorsum(int); 
int main() 
{ 
    int i, j, s = 0, t, m; 
    for (i = 24; i <= 28123; i++) //sum of 2abundant nos start from 24 
    { 
     for (j = 12; j <= i/2; j++) { 
      t = factorsum(j); 
      if (t > j) { 
       m = i - j; 
       t = factorsum(m); 
       if (t > m) { 
        s = s + i; 
        break; 
       } 
      } 
     } 

    } 
    j = 0; 
    for (i = 1; i <= 28123; i++) 
     j = j + i; 
    printf("\n%d", (j - s)); 
    return 0; 
} 

int factorsum(int j)  //checking sum of factors 
{ 
    int k, s = 0; 
    for (k = 1; k <= (j/2); k++) { 
     if (j % k == 0) { 
      s = s + k; 
     } 
    } 
    return s; 
} 

Answer 1

즉각적인 큰 최적화는 제수 합계를 미리 계산하는 것입니다. 현재 i에 대해 j = 12, ...에 대해 factorsum(j)을 다시 계산합니다. 제수 합계를 한 번 계산하여 배열에 저장하면 O(j/2) 계산 대신 빠른 (O(1)) 조회가됩니다.

그게 내 상자의 작동 시간을 3 분 30 초에서 1 초로 단축시킵니다.

다음 개선 사항은 제수 합계를 계산할 때 더 나은 전략을 사용하는 것입니다. 각각의 숫자를 j/2으로 나누지 않고 j을 나눌 지 여부를 확인하는 대신 제본자가 (d, j/d) 인 쌍을 사용하여 √j까지만 검사 할 수 있습니다 (완벽한 사각형에는주의를 기울여야합니다. 한 번만 제곱근을 추가해야합니다).

이렇게되면 0.05 초가 소요됩니다.

하지만 배열의 합계를 저장하는 경우, 당신은 논리를 반전 대신 한 번에 하나 개의 번호 n을 고려하고 약수를 찾는하여 더 나은 할 수있는, (k*d)를 하나 개의 제수 d을 고려하고 모든 배수를 찾을 수 . 이는 제수 합계를 계산하는 데 필요한 시간을 O(limit^1.5) (또는 j/2까지 나눌 경우 O(limit^2))부터 O(limit * log limit)까지 줄입니다. (참고 : 절대 제한이 부여되었으므로 여기서는 복잡성 표기법을 엄격하게 적용하지 않습니다. 두 개의 풍부한 숫자를 합한 숫자가 아닌 limit 인 숫자를 찾으려고합니다.

0.03 초입니다.