Chapter-8 NumberTheory 第8章 数论 - Sieve 筛选算法

问题

素数是除了 1 和它自身没有其他数能够整除的正整数，最小的素数是 2 。而不符合该特性的正整数是合数。素数是数论学科中的基础概念，关于素数的最为著名的问题就是哥德巴赫猜想。

判断 1 - n 中见的任意一个整数是不是素数。常见的素数有 2, 3, 5, 7, 9, 11, 13, 17, 19, 23 等等。

解法1

基本判断

判断一个正整数 x 是否为素数，按照素数的定理，只要不断计算 result = x times i （ 1 le i le x ），累加得到result

埃拉托斯特尼（Eratosthenes）筛选法

设置一个数组 s = [1…n] ，每个位置 s[i] 为 true 表示它是素数，否则为合数。

(1) 从 2 开始， 2 为素数，以 2 为筛子，留下2，删去所有2的倍数
//2之后第一个未被删除的数是3，则3为素数，以3为筛子，留下3，删去所有3的倍数
//3之后第一个未被删除的数是5，则5为素数，以5为筛子，留下5，删除所有5的倍数
//以此类推…
//当求解的数字范围较大时可以使用long long这样的数据类型

这样每次查找单词时，按照前缀从根节点开始向下匹配每个孩子节点的字符即可。前缀树查找一个长度为 n 的单词的时间复杂度为 O(n) 。