基础
命题：对于数列 $f(x)=x^2+1$ ，证明其中包含无穷多个素数。
筛法定义
定义筛法，求小于等于$m$的所有满足 $f(m)$为素数的数。核心思想：通过按顺序不断筛除使得 $f(n)$ 不为素数的 $n$，最终剩下的满足条件 $f(n)$ 为素数的数。
算法步骤:
- 初始化一个状态数组（为了方便，数组从1开始编号），长度为$m$，状态均为未被筛除。这个数组表示对于位置 $i$, 处于筛除状态则表示该位置为合数，否则为素数。
- 位置变量 $i$ 初始化为1，执行如下迭代操作, 计算 $f(i)$ 的所有素因子 $p_1, p_2, \dots, p_k$，并将状态数组中所有位置为 $pos = p_{j} \cdot q + i(j = 1, 2, \dots, k, q \in \mathbb{N}, 1 <= q <= \lfloor \frac{n - i}{p_j} \rfloor)$ 的值设置为已被筛除，最后将位置变量+1执行下次循环。
- 当位置变量 $i$ 大于 $n$ 时，算法结束。
证明：为何上述的筛法能够筛除所有满足条件 $f(n)$ 为素数的 $n$ ？
- 为什么能将位置 $pos = p_{j} \cdot q + i$ 的数筛除？因为 $f(pos) = (p_{j} \cdot q + i)^2 + 1 = p_{j}^2 q^2 + 2*p_{j}*q + i^2 + 1$ ，显然 $p_{j}$ 为 $f(pos)$ 的一个素因子，即 $f(pos)$ 为合数。
- 使用归纳法，假设对于小于等于 $k$ 的所有数，执行上述筛法都能够准确判断 $f(n)$ 是否为素数。则当 $n = k+1$时，存在以下两种情况：
- 位置 $n$ 的状态为已筛除，根据1可以证明符合要求。
- 位置 $n$ 的状态为未筛除，则需要证明 $f(n)$ 为素数。使用反证法，假设 $f(n)$ 为合数，取其最小的素因子 $p_{min}$, 由于 $p_{min} \mid ((k+1)^2 + 1)$ ，显然有 $p_{min} < k$ 。取 $r = k + 1 - p_{min}$，则有 $f(r) = (k+1-p_{min})^2 + 1 = p_{min}^2 - 2(k+1)p_{min}+((k+1)^2+1)$ ，显然 $p_{min}$ 为 $f(r)$ 的一个素因子。由于 $r \leq k$, 故根据筛法的算法流程必然会操作到位置 $r$，且在操作到位置 $r$ 的时候会执行位置 $p_{min} \cdot 1 + r = k + 1$ 的筛除，与条件矛盾。
基于以上，可以证明上述的筛法可以筛出给定范围所有满足 $f(n)$为素数的数。
无穷性证明
- 假设 $f(n)$ 仅包含有限个素数，假设 $k$为满足 $f$为素数的最大数，即取任意 $n \gt k$ 执行筛法时，有 $ \forall i(i \gt k, i \lt n)$ 均会被筛除。
设 $P_i$ 表示$f(i)$ 的素因子集合，$S_n = \bigcup_{i=1}^n P_i$
n的取法：
- $S_n$ 连乘
- $S_n$ 最大素数内的所有素数连乘，p_{m} | p1…pk
- $2 * f_{k}$
取$n$, 根据假设，
- 必然存在 $p_{m} \mid f(q) = q^2 + 1, n - q \equiv 0 \pmod {p_{m}}, k < q < n$, 且位置 $q$ 也会被筛除。且 $p_{m} \notin S_n$
$ p_{t} | n^2 + 1 $ 2. $\forall i(i \gt k, i \lt n), f(i)$ 均为合数。
记函数 $g(x)$表示执行筛法时，位置 $x$ 第一次被筛除的位置， 若始终未被筛除，取 $g(x) = x$, 则有：$g(1)=1,g(2)=2,g(3)=1,g(4)=4,g(5)=1,g(6)=6,g(7)=1$, 等价于证明: $\forall x > k, g(x) \lt x$. 显然g(n) > k，
g(q) > k
考虑两种情况：
- 位置 $q$ 在执行到$k$时已被筛除，
- 位置 $q$ 在执行到$k$时未被筛除，
n - q + q_{2} + 1
$f(n)$为素数的条件是 $\forall i (1 \leq i < n), (n - i, i^2+1)=1$
证明: 使用反证法，假设 $f(n)$ 仅包含有限个素数，分别为 $n_1, n_2, \dots, n_k$, 其中 $n_1 < n_2 < \dots < n_k$ ,
设集合 $S_n = \Set{f(i), i=1, 2, \dots, n_k}$, 取集合 $S_p$中每个数的素因子组成一个全集，设为 $S_p$。设 $m = \prod p_i, p_i \in S_p$
暂时不用的东西：对应的值分别为 $p_1=f(n_1), p_2=f(n_2), \dots, p_k=f(n_k)$, 使用集合 $S_p=\Set{p_1, p_2, \dots, p_k}, S_n=\Set{n_1, n_2, \dots, n_k}$表示。 设 $\displaystyle m = \prod_{i=1}^k p_i$
根据假设有 $f(m)$ 不是素数。不妨设 $f(m)$ 最小的素因子为 $p_{t_{1}}$，显然有:
- $p_{t_{1}} \notin S_p$
- $p_{t_{1}} < m$
取 $r_{t_{1}} = m \bmod p_{t_{1}}$，则有 $p_{t_{1}} | f(r_{t_{1}})$ 。
若$p_{t_{1}} = f(r_{t_{1}})$推出矛盾，则必然有$p_{t_{1}} > r_{t_{1}} + 1$ 且存在 $p_{t_{2}}$ 满足 $p_{t_{2}} | f(r_{t_{1}})$ 并满足 $p_{t_{2}} < r_{t_{1}}$。取 $r_{t_{2}}=r_{t_{1}} \bmod p_{t_{2}}$, 则有 $p_{t_{2}} | f(r_{t_{2}})$.
若能证明 $p_{t_{2}} \notin S_p$，则可以推出矛盾。因为：若$p_{t_{2}} = f(r_{t_{2}})$推出矛盾，否则有 $p_{t_{2}} > r_{t_{2}} + 1$ 且存在 $p_{t_{3}}$ 满足 $p_{t_{3}} | f(r_{t_{2}})$ 并满足 $p_{t_{3}} < r_{t_{2}}$, 取 $r_{t_{3}}=r_{t_{2}} \bmod p_{t_{3}}$, 则有 $p_{t_{3}} | f(r_{t_{3}})$.由于是一个不断放缩的过程，则必然存在一个$i$ 使得 $p_{t_{i}} = f(r_{t_{i}})$.
核心难点在于证明：$p_{t_{i}} \notin S_p$ ???
可以修改的点: m的构造方式以及$p_{t_{i}}$的构造方式
思路
设 $f(n)$ 的最大素因子为 $p$, 则取函数
$$ g(n) = \begin{cases} 0, & p < n \ p, & p \gt n \end{cases} $$
可以证明：若 $f(n)$ 为合数，等价于 $\exists i \in [1,\cdots,n-1]$ 满足 $g(i) \mid n - i$，且 $g(i) \neq 0$。
$g(n)$的性质：
- $g(n) \mid f(n)$
- 同一个值在 $g(n)$ 序列中最多出现两次，且 $g(g(n) - n) = g(n)$, 例如 $g(2)=5$ 有 $g(g(2)-2)=g(3)=5$