线性筛是一种O(N)时间复杂度的算法，用于高效筛出1到N之间的所有质数，并能同时预处理最小质因子、欧拉函数、约数个数等数论函数。相比埃氏筛的O(N log log N)复杂度，线性筛通过确保每个合数仅被其最小质因子筛除一次来实现线性复杂度，核心在于当i能被当前质数p整除时立即终止内层循环。该算法不仅能筛质数，还支持多种数论函数的递推计算，如欧拉函数和约数个数，使其成为处理大规模数论问题的有力工具。

对于模式串pattern[0…m-1]，前缀函数π[i]表示：子串pattern[0…i]中，最长的相等前缀和后缀的长度；前缀和后缀不能是子串本身（否则长度就是 i+1，没有意义）。索引 i子串 pattern [0…i]可能的相等前后缀最长长度 π[i]0“A”无（只有 1 个字符）01“AB”前缀 “A”、后缀 "B"→不相等02“ABA”前缀 “A”、后缀 "A"→相等；前缀 “AB”、后缀