质数是一类非常特殊的数，也有一些非常优美的性质，这里整理一些涉及到质数性质的问题。
1. 素数个数的位数
题目链接：NEFU117
题目大意：求1 ~ 10^n之间质数的个数。
记质数的个数为$\pi(n)$,根据质数定理可知，
$$ \lim_{n \rightarrow \infty} \frac{\pi(n)}{\frac{n}{\ln n}} = 1$$
因此答案即为$\lg(\frac{n}{\ln n})$。
2. f(n)
题目链接：hdu2582
题目大意：求$f(n)$，其中：
$f(n) = Gcd(3)+Gcd(4)+…+Gcd(i)+…+Gcd(n)$
$Gcd(n)=gcd(C[n][1],C[n][2],……,C[n][n-1])$
关于$Gcd(n)$的值，有如下定理：
记$Gcd(n) = gcd(C[n][1], C[n][2], \dot, C[n][n-1])$,其中gcd表示这些数的最大公约数，$C[n][i]$为组合数。则
- 若$n$仅含有一个质因子即为$p^k$的形式，则$Gcd(n) = n$
- 若$n$含有多个质因子，则$Gcd(n) = 1$
知道这个定理之后，我们仅需预处理出每个数的质因子个数即可。
3. A New Change Problem
题目链接：hdu1792
题目大意：有两种面额互质的硬币，每种硬币有无限个，问仅用这些硬币不能组合出的面额最大是多少，以及有几种不能组合出的面额。
这也是一个定理，描述如下：
给定两个互质的正整数A和B，那么它们最大不能组合的数为$A × B - A - B$，不能组合数的个数为$(A - 1) × (B - 1) / 2$。
有了上述定理，这个题目就变得非常简单。
4. Fibonacci质数
题目链接：nyist468
题目大意：定义$Fibonacci$质数为仅能被$fibonacci$数列中的$1$和它本身整除的$Fibonacci$数，给出$n$，问$F_n$是否为$Fibonacci$质数。
对于$Fibonacci$数，有如下定理：
设$F(n)$为$Fibonacci$数列的第$n$项，则$gcd(F(m), F(n)) = F(gcd(m, n))$
我们要判断的相当于对任意 $0 < m < n$ , 是否有$gcd(F(m), F(n)) = 1 = F(1)$, 即对任意$0 < m < n$， 是否有$gcd(m, n) = 1$, 这其实就是判断$n$是否为质数。
这道题的n的范围为$10^{18}$,需要用到Miler-Rabin测试来做质数判定。
5. Prime Distance
题目链接：poj2689
题目大意：在$L$ ~ $U$范围内，相邻质数的距离最大和最小分别是多少。
这道题并不涉及什么定理，仅是在判断一个数是否为质数时采用了一些小技巧。题目中数据范围为 $2^{32}$ ,就算采用线性筛法也会超时。但注意到 $L$ ~ $U$ 的区间长度为$1000000$，这提醒我们要在这上面做文章。我们根据线性筛法的原理可以发现，每个数仅被它最小的质因数筛去。因此我们可以预处理出 $\sqrt{2^{32}}$ 内的质数，则 $2^{32}$ 内的合数均可被该范围内的质数筛去。预处理出质数后，再用线性筛法筛出$L$ ~ $U$范围内的质数即可。