正整数n的约数问题.cpp

（一） 求a~b 之间各个数的约数个数之和。(其中包括a和b在内) ans = sigma(f(i)) , (a <= i <= b) , 其中f(i)表示i的约数的个数

/*
（一）
求a~b 之间各个数的约数个数之和。(其中包括a和b在内)
ans = sigma(f(i)) , (a <= i <= b) , 其中f(i)表示i的约数的个数 
*/
#include<iostream> 
#include<algorithm> 
#include<cmath> 
using namespace std;
typedef long long elem_t ;

elem_t Cal(elem_t n) //1~n之间各个数的约数个数之和，包括n
{ 
    if(n == 0) return 0 ; 
    int i ; 
    elem_t ans = 0 ; 
    for(i = 2 ; i <= sqrt(double(n)) ; i++) 
    { 
        ans += n/i ; 
    } 
    int mid = int(sqrt(double(n))) ; 
    ans += ans + n-mid*mid ; 
    ans += n ;  
    return ans ; 
} 

int main() 
{ 
    elem_t a , b ; 
    while(cin>>a>>b) 
    { 
        if(a == 0 && b == 0) break; 
    //    cout<<Cal(a)<<"  "<<Cal(b)<<endl; 
        elem_t ans = Cal(b) - Cal(a-1) ; 
        cout<<ans<<endl; 
    } 
    return 0 ; 
} 


/*
（二）
题意：对于给定的自然数n和k（1≤n＜，1≤k＜20），求的所有正整数因子的和
解答: 对于任意大于等于2的正整数n ，可以表示成为：n = p1^e1 * p2^e2 *...* pr^er ;
							   n^k 可以表示成为：n^k = p1^(e1*k) * p2^(e2*k) *...* pr^(er*k) ;
	  其中，pi 为素数，p1 < p2 < ... < pr , 且ei为任意正整数。
sum = (1 + p1 + p1^2 + ... + p1^(k*e1)) * 
	  (1 + p2 + p2^2 + ... + p2^(k*e2)) *
	  ... *
	  (1 + pr + pr^2 + ... + pr^(k*er)) ;
利用等比数列的求和公式，可以改进公式为：
sum = (p1^(k*e1+1) - 1)/(p1 - 1) + (p2^(k*e2+1) - 1)/(p2 - 1) + ... + (pr^(k*er+1) - 1)/(pr - 1) ;
*/

/*
（三）
题意：正整数n个约数的个数
解答：
	若正整数n可分解为p1^a1*p1^a2*…*pk^ak (其中pi为两两不同的素数,ai为对应指数)
	n的约数个数为: ans = (1+a1)*(1+a2)*….*(1+ak) ;
*/