今天要说的题目来源于 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;
}

留言