요인 합계 찾기

Question

왜이 코드는 숫자의 합계를 반환합니까?

여러 Project Euler 문제에서 문제의 일부로 요소 합계를 계산해야합니다. 포럼 중 하나에서, 누군가가 실제로 개인 요소를 찾지 않아도되고, 주요 요소만을 찾을 필요가 없기 때문에 누군가가 다음 합계를 찾는 가장 좋은 방법으로 다음 Java 코드를 게시했습니다 (자바를 알 필요가 없으며 아래 내 요약으로 건너 뛸 수 있습니다.) :

public int sumOfDivisors(int n) 
{ 
    int prod=1; 
    for(int k=2;k*k<=n;k++){ 
     int p=1; 
     while(n%k==0){ 
      p=p*k+1; 
      n/=k; 
     } 
     prod*=p; 
    } 
    if(n>1) 
     prod*=1+n; 
    return prod; 
} 

이제 여러 번 시도해 보았습니다. 질문은, 왜?

100 : 1,2,4,5,10,20,25,50,100을 고려하십시오. 합계는 217입니다. 프라임 인수 분해는 2*2*5*5입니다. 이 함수는 [5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217

팩터링 8 : 1,2,4,8을 제공합니다. 합계는 15입니다. 프라임 인수 분해는 2*2*2입니다. 이 기능은 알고리즘은 (요인 F 또는 F 서브 I의 i 번째 인덱스를 의미하는 Fi 사용)로 귀결 당신에게 [2*(2*(2+1)+1)+1]=15

을 제공합니다 m 고유 소인수의 수입니다

return product(sum(Fi^k, k from 0 to Ni), i from 1 to m) 

을 Ni입니다 각각의 고유 한 요소가 소수 분해에서 발생하는 횟수.

이 공식은 요인의 합계와 같은 이유는 무엇입니까? 내 생각에 분산 속성을 통한 소수 요소 (예 : 모든 고유 요소)의 모든 고유 한 조합의 합계와 같지만 어떻게 보이지 않습니다.

Answer 1

가장 간단한 경우를 살펴 보겠습니다. n은 소수의 거듭 제곱입니다.

k^m의 인수는 1, k, k^2, k^3 ... k^m-1입니다.

이제 알고리즘의 내부 루프를 살펴 보자 : 첫 번째 반복 후

, 우리는 k + 1 있습니다.

는 두 번째 반복 한 후, 우리는 숫자에 대해 어떻게 작동하는지

---

는 그의 ... k(k+1) + 1, 또는 k^2 + k + 1

세 번째 반복 한 후, 우리가에 k^3 + k^2 + k + 1

그리고이 있습니다 그것은 단일 소수의 힘입니다. 나는 앉아서 이것을 모든 숫자로 일반화 할 수도 있지만, 먼저 자신에게 가야 할 수도 있습니다.

EDIT : 이제 이것이 받아 들인 대답이되었으므로 두 가지 별개의 주요 요인을 가진 알고리즘에서 알고리즘이 어떻게 작동하는지 보여줌으로써 좀 더 자세히 설명 할 것입니다. 그런 다음 임의의 양의 별개의 소수 요소가있는 숫자로 일반화하는 것은 간단합니다. x^i.y^j의

요소는 x^0.y^0, x^0.y^1 ... x^0.y^j, x^1.y^0입니다 ...

각 별개의 소수 요소에 대한 내부 루프는 x^i + x^i-1 + ... + x^0을 생성합니다 (마찬가지로 y). 그렇다면 우리는 단지 그것들을 곱하면 우리는 우리의 합계를가집니다.

Answer 2

알고리즘은 본질적으로 n의 인자 세트와 유사한 n의 프라임 팩터의 모든 주문 된 부분 집합을 조사합니다.