02prime.tex

\chapter{素数}
\begin{introduction}[本章内容提要]
	\item 质因数分解
	\item 筛选素数
	\item 大区间问题
	\item 梅森素数
	\item 完全数
	\item 因数之和函数
\end{introduction}

\section{质因数分解}
\begin{definition}{素数}{prime}
	素数$p$是大于1且它的因数只有1和$p$的整数。
\end{definition}

\begin{property}
	\label{pro:prime}
	令$p$是素数，假设$p$整除乘积$ab$，则$p$整除$a$或$p$整除$b$(或者$p$既整除$a$也整除$b$)。  
\end{property}

\begin{theorem}{无穷多素数定理}{label}
	存在无穷多个素数。
\end{theorem}

\begin{proof}
	证明的思路是，假设我们现在有一个素数表，只要说明如何利用这些素数找出新的不在表中的素数，这样迭代下去，就
表明必有无穷多个素数。设素数表一开始为$p_1,p_2,...,p_n$，令$A = p_1p_2...p_n + 1$，设$q$是某个整除$A$的素数，且设其是
最小的那个，那么$q$一定不在最初的素数表中，因为如果$q=p_i$，则$q$能整除1，显然错误。于是我们可以无限扩充素数表。
\end{proof}

\begin{theorem}{素数定理}{label}
	当x很大时，小于x的素数的个数近似等于$x/ln(x)$，即
	$$
	\lim_{x\to\infty} \frac{\pi(x)}{x/ln(x)}=1
	$$
	其中$\pi(x)$为素数计数函数，$\pi(x) = \#\{prime\ p:p\le x\}$。
\end{theorem}

\begin{theorem}{素数整除性质}{label}
假设素数$p$整除乘积$a_1a_2...a_r$ ，则$p$整除$a_1 \quad ,a_2 \quad , ...,\quad a_r$ 中至少一个因数。
\end{theorem}

\begin{proof}
	使用上面的\hyperref[pro:prime]{性质}可以方便的证明该定理。
\end{proof}

\vbox{}

下面将用{\heiti 素数整除性质}证明每个正整数可唯一分解成素数的乘积（算术基本定理）。

\begin{theorem}{算术基本定理}{suanshu}
	每个整数$n>=2$可唯一分解成素数乘积$n=p_1p_2...p_r$。
\end{theorem}

\begin{proof}
算术基本定理包含两个断言：

断言1：数$n$可以以某种方式分解成素数的乘积；

断言2：仅有一种这样的因数分解方式（因数重排除外）；

- 对于断言1的证明用到归纳证明法 （当$N+1$是合数时，其必然可以分解成$N+1=n_1*n_2$，而前面已经归纳完毕，即$n_1,\ n_2$一定可以分解成素数，因此得证）。

- 对于断言2，可以由定理\ref{thm:suanshu}证得。
\end{proof}

\vbox{}

下面考虑如何进行质因数分解。

简单直接的方法是试除$2,3,4,5,...$分解$n$，但效率较低。
考虑一个整数$n$，如果$n$本身不是素数，则必有整除$n$的素数$p\leqslant \sqrt{n}$ 。于是我们可以遍历$2\sim \sqrt{n}$
进行试除，时间复杂度为$O(\sqrt{n})$。如果提前预处理出所有素数，则可每次只试除素数，时间复杂度为$O(\frac{\sqrt{n}}{ln \sqrt{n}})$。

\lstinputlisting[language=C++, style=codestyle2]{code02/factor.cpp}

\section{区间素数筛}

这里区间素数筛指的是给定一个上限$n$，要求出区间$[1,n]$中所有的素数。如果采用直接遍历每个数并判断是不是素数的方法，时间复杂度为$O(n^{3\over2})$，若$n>10^6$，则
不能在$1s$的时间内求解。下面介绍的两种筛法，均使用“筛选”的思想，时间复杂度分别为$O(nlog(logn))$和$O(n)$，在比赛中经常使用。

\subsection{埃氏筛法}
考虑如果一个数$n$如果是合数(非素数)，那么它一定有小于等于$\sqrt{n}$的质因子，也即$n$是这个质因子的倍数。那么我们可以从小到大($2\sim n$)依次遍历每个数，并存在一些标记记录每个数是否是合数，当遍历到某个数
时，如果当前数没有被标记为合数(就一定是素数了)，就把当前数的所有倍数标记为合数。代码如下：

\lstinputlisting[language=C++, style=codestyle2]{code02/aishi.cpp}

\begin{remark}
	代码中有两个关键的地方：
\begin{itemize}
	\item 第10行，只有当是素数时，才进行筛选,因为使用合数筛是多余的(该合数的质因子已经筛过了)；
	\item 第12行，从$i*i$开始筛，因为$(i-1)*i,\ (i-2)*i,\ ...\ 2*i$已经被筛过了。
\end{itemize}
\end{remark}

考虑埃氏筛法的时间复杂度，由于每次只考虑素数去筛，即为：
$$
	n\sum_{p\le n} \frac{1}{p}\ , \quad p \ is \ prime
$$
上式可近似认为是$O(nloglogn)$，感兴趣的可以阅读\href{http://www.wikiwand.com/en/Sieve_of_Eratosthenes#/Algorithm_complexity}{Sieve\_of\_Eratosthenes\#/Algorithm\_complexity} 

\vbox{}

观察埃氏筛法，是否有重复被筛去的合数呢？有的，就是一些质数的较大的公倍数，比如12，当i=2时(从4开始)会筛12;当i=3时(从9开始)还会筛12。

\subsection{欧拉线性筛法}

	欧拉筛的思想是{\heiti 保证每个合数都被其最小的质因子筛去}，这样就不会像埃氏筛那样重复筛某个数。

	首先其还是筛选法，考虑用什么筛的：对于每个i，乘以小于i的每个素数，直到能整除就停止，这样能保证每个数只被筛去一次。
	
	这个整除停止很关键，假设没有这个break，就会有很多重复。
	
	比如$i=6$，取质数3，筛去了18；$i=9$，取质数2，也筛去了18。
	
	再比如$i=6$，取质数5，筛去了30；$i=10$，取质数3，筛去了30；$i=15$，取质数2，筛去了30。
	
	如果加上break，则筛去18的是9*2，筛去30的是15*2。为什么18不会被6*3筛去？ 因为$6\%2=0$
	提前break了。即若有一个素数$p|i$,则我用i和后面更大的素数去筛选，不如用p和更大的i去筛选，
	这样保证了筛掉每个数的是其最小质因子。
	
	
\lstinputlisting[language=C++, style=codestyle2]{code02/euler.cpp}

由于每个数只会被筛去一次，时间复杂度是$O(n)$。

\subsection{区间数的最大、最小质因子}
上面介绍的埃氏筛法和欧拉筛法经过一点改动就可以用来求区间数的最大质因子和最小质因子。

对于区间最大质因子，稍微增加点埃氏筛的复杂度，从$2*i$而不是$i*i$开始筛：

\lstinputlisting[language=C++, style=codestyle2]{code02/maxprime.cpp}

对于区间最小质因子，只需修改欧拉筛中标记数组即可，时间复杂度不变：

\lstinputlisting[language=C++, style=codestyle2]{code02/minprime.cpp}


\section{区间质因数分解}
这里区间质因数分解指的是给定一个上限$n$，要求出区间$[1,n]$中所有数质因数分解的结果。
可以用埃氏法先求出所有数的所有质因子；或者使用欧拉法求出区间数的最小质因子再利用区间信息求解。
\subsection{埃氏法}
先$O(nlogn)$求出每个数的所有质因子，再$O(nlogn)$直接除求出质因子对应的指数：

\lstinputlisting[language=C++, style=codestyle2]{code02/interaishi.cpp}

\subsection{欧拉法}
先$O(n)$欧拉筛求出每个数的{\heiti 最小质因子}，再$O(nlogn)$利用区间信息求出对应的指数。
区间信息指的是，对于每个数如果我们都知道其最小质因子，则可以先将当前数的最小质因子除完，剩下的数的最小质因子我们还是知道的，于是继续除，直到1为止。
\lstinputlisting[language=C++, style=codestyle2]{code02/intereuler.cpp}

\section{大区间素数筛与质因数分解}
大区间指的是咱们考虑的区间不再是$[1,n]$，而是$[L,R]$，这里$R\le 2^{40}, \  R-L<=10^6$。

\subsection{大区间素数筛}
对于一个合数$n$，一定有小于等于$\sqrt{n}$的质因子，利用这一点，我们依然可以使用埃氏筛的思想。
先预处理出$[1,\sqrt{R}]$区间内的所有素数，然后拿这些素数去做筛选即可。

时间复杂度为$O(N + llogl)$ ， 其中$N$为$\sqrt{R}$，$R$是区间右端点，即需要预处理的素数范围 ； $l$为区间长度$R-L$。

\lstinputlisting[language=C++, style=codestyle2]{code02/large-inter-prime.cpp}

\subsection{大区间质因数分解}
和上面类似，先埃筛求出小于等于$\sqrt{R}$的所有质因子，然后对于区间内的每个数直接除即可。

因为一个合数n大于$\sqrt{n}$ 的质因子最多只有1个，因此将已知的质因子全部除尽后，若不为1，就为那个大于$\sqrt{n}$的质因子，对应指数为1。

时间复杂度为$O(N + llogl)$，其中$N$为$\sqrt{R}$，$R$是区间右端点，即需要预处理的素数范围 ； $l$为区间长度$R-L$。

\lstinputlisting[language=C++, style=codestyle2]{code02/large-inter-factor.cpp}


\section{梅森素数与完全数}
梅森素数与完全数在程序设计竞赛中不是很常见，这里简要介绍一下。

\subsection{梅森素数}
现在我们来研究形如$a^n-1(n\ge2)$的素数。例如31就是这样的数，因为$31 = 2^5 - 1$。
由于$a-1$始终是$a^n-1$的因子。为啥呢？因为使用几何级求和公式：（展开即可证明该公式）
$$
x^n-1=(x-1)(x^{n-1}+x^{n-2}+...+x^2+x+1)
$$
所以若$a^n-1$为素数，则a一定等于2。反之显然不成立。

再进一步考虑$n$，假设$n$为合数，即$n=mk$，则$2^n=2^{mk}=(2^m)^k$。使用$x=2^m$的几何级数公式得：
$$
2^n - 1 = (2^m)^k - 1 = (2^m-1)((2^m)^{k-1}+(2^m)^{k-2}+...+(2^m)^2+(2^m)+1)
$$
这证明了若$n$是合数，则$2^n-1$也是合数。综上有以下命题：

\begin{proposition}{}{label}
	如果对整数$a\ge2$与$n\ge2$，$a^n-1$是素数，则$a$必等于2且$n$一定是素数。
\end{proposition}

形如$2^p-1$的素数叫做{\heiti 梅森素数}，已知的梅森素数在\href{https://www.mersenne.org/primes/}{https://www.mersenne.org/primes/}中可以找到，
目前已经找到了51个(截至2019.09.03)。发现更多的梅森素数没有太大的数学意义，数学上更令人感兴趣的是下面的问题，其答案尚未知晓：

\begin{custom}{问题}
	存在无穷多个梅森素数吗？
\end{custom}

\subsection{完全数}

\begin{definition}{完全数}{wanquanshu}
	完全数是等于其真因数之和的数。真因数指的是小于自己的因数(即除去自己)。
\end{definition}


\begin{theorem}{欧几里得完全数公式}{label}
	如果$2^p-1$是素数，则$2^{p-1}(2^p-1)$是完全数。
\end{theorem}

\begin{proof}
	将$2^{p-1}(2^p-1)$所有真因数直接写出求和即证。
\end{proof}

这里的$(2^p-1)$不就是梅森素数吗？也就是说只要求得一个梅森素数，就得到一个完全数。

那欧几里得完全数公式是否表示了所有完全数呢？千年之后的欧拉证明了欧几里得完全数公式至少给出了所有{\heiti 偶完全数}，称为欧拉完全数定理。

在介绍和证明欧拉完全数定理之前，我们先来介绍一个函数$\sigma(n)$。

\begin{center}
	$\sigma(n) = n$的所有因数之和(包括1和n)。
\end{center}

例如$\sigma(6) = 1 + 2+3+6 = 12$。下面试着写出其一般公式，$\sigma(p) = p+1$，$\sigma(p^k) = 1 + p+p^2+...+p^k = \frac{p^{k+1}-1}{p-1}$。

如果你用程序打个表，也许会发现$\sigma(mn)$时常会等于$\sigma(m)\sigma(n)$，实际上这在$m$和$n$互质时成立。

\begin{theorem}{$\sigma$函数公式}{label}
	\begin{itemize}
		\item 如果$p$是素数，$k\ge1$，则$\sigma(p^k) = 1 + p+p^2+...+p^k = \frac{p^{k+1}-1}{p-1}$；
		\item 如果$gcd(m,n)=1$，则$\sigma(mn) = \sigma(m)\sigma(n)$。
	\end{itemize} 
\end{theorem}

$\sigma$函数在程序设计竞赛中也时常出现(或者其类似函数，如因子个数函数)，后面章节还会说到它，现在我们用它来辅助证明欧拉完全数定理。

显然，$\sigma$函数可以和完全数产生联系，如果$\sigma(n)=2n$，则n恰好是完全数。

\begin{theorem}{欧拉完全数定理}{label}
如果n是偶完全数，则$n$一定是$2^{p-1}(2^p-1)$ 的形式，其中$2^p-1$是梅森素数。
\end{theorem}

\begin{proof}
	假设n是偶完全数，n是偶数则说明可将它分解成$n=2^km,\quad k\ge 1 \ \&\ m\ is\ odd$
	
	则$\sigma(n)=\sigma(2^km)=\sigma(2^k)\sigma(m)=(2^{k+1}-1)\sigma(m)$。
	又n是完全数，则$\sigma(n)=2n=2^{k+1}m$。
	
	因此可以得到
	$$
	2^{k+1}m=(2^{k+1}-1)\sigma(m)
	$$
	由上式可知，由于$(2^{k+1}-1)$一定是奇数，所以$2^{k+1}| \sigma(m)$ ,于是设$\sigma(m)=c*2^{k+1}$ ,带入上式有：
	\begin{align*}
	2^{k+1}m=(2^{k+1}-1)*c*2^{k+1} \\
	m=(2^{k+1}-1)*c
	\end{align*}
	现在我们有两个式子，$m=(2^{k+1}-1)*c$ 和$\sigma(m)=c*2^{k+1}$。
	
	实际上这里c只能等于1，下面我们来证明$c=1$。
	
	假设$c>1$，则$m=(2^{k+1}-1)*c$至少被不同的数$1,c,m$所整除，因此有
	$$
	\sigma(m)\ge 1+c+m=1+c+(2^{k+1}-1)*c
	$$
	显然，这是错误的(会得出$0\ge 1$)，因此$c=1$，所以$m=2^{k+1}-1$  ，  $\sigma(m)=2^{k+1}=m+1$，所以m是素数。
	
	现在我们已经证明了，如果n是偶完全数，则
	$$
	n=2^k(2^{k+1}-1)\ ,\quad where \ (2^{k+1}-1)\ is \ prime
	$$
	由于$2^{k+1}-1$是素数，则$(k+1)$一定是素数，（上节已说明）。令$k+1=p$，则$n=2^{p-1}(2^p-1)$，其中$2^p-1$是梅森素数。
	
	欧拉完全数定理证毕。
\end{proof}

\vbox{}

\begin{note}
	关于完全数的几个结论：
	\begin{itemize}
		\item 目前还没找到奇完全数
		\item 每个完全数的全部因数倒数之和都是2
		\item 除了6以外的完全数，每个都可以表示成连续奇数的立方和
		\item 每个完全数都可以表示成2的一些连续正整数次幂之和
		\item 完全数都是以6、8结尾
	\end{itemize}
\end{note}

\vbox{}

\begin{custom}{问题}
	存在奇完全数吗？
\end{custom}

\vbox{}

\vbox{}


\begin{problemset}
	\item 区间数的最大质因子是否有线性时间的算法？
	\item 大区间数的最小质因子是否有线性时间的算法？
	\item 试着写出求单点$\sigma(n)$以及区间$[1,n]$所有$\sigma$值的代码。
\end{problemset}