分解质因数

今天要说的题目来源于 Soldier and Number Game. 这道题到底干什么呢，说白了就是求两个数$1 \le b \le a \le 5 000 000$之间的所有数的质因数数目之和。快速求解一个数的质因数数目是这道题的关键。

Sieve of Eratosthenes 是这道题的关键。这是一个求解质数/质数判定的方法，其思想是筛选出一个质数的整数倍，质数的整数倍必然不是质数，所以都被筛选出去。在没有筛选的结果中继续求解当前最小数字的整数倍，直至筛完为止。其 C++ 代码如下所示：

Sieve of Eratosthenes
1
2
3
4
5
6
7
8
9
10
11
12
// prime number table from 2 to 5000000
// those who have number 0 are prime numbers.
int table[5000001];
void build_table(){
    const int limit = sqrt(5000000)+1;
    table[0]=table[1]=-1;
    for(int i=2; i<=limit; i++)
        if(!table[i])
            for(int j=2; j*i<=5000000; j++)
                table[i*j]=i;
}
int isprime(int i){return !table[i];}

你可以发现，在这个质数表中实际上还存储了每个数字的一个质因数。要提取出一个数的完整质因数分解，只要依据基本法a/=table[a]不断迭代就可以了。

但是如果按照这样的思路去数每个数的质因数个数的话，在原题中还是会超时。其一个原因是我们要求的是质因数的个数，其可以在建立质数表的时候完成。其二，求从 a 到 b 中每个质因数的个数之和，倾向于使用部分和的方法。

那么怎么求每个数的质因数个数呢，在 Sieve of Eratosthenes 的基础之上？

Number of Prime Factors
1
2
3
4
5
6
7
8
void build_table(){
    //const int limit = sqrt(5000000)+1;
    //table[0]=table[1]=-1;
    for(int i=2; i<=5000000; i++)
        if(!table[i])
            for(int j=i; j<=5000000; j+=i)
                table[j]=table[j/i]+1;
}

留言

▲