《准素数模型》简介.PDF

《准素数模型》简介 冯军刚 （西安石油大学） 1.传统的筛法模型 传统筛法是以直接筛选出全部 “素数”为目的而设计的，所以它的筛除方法就是只筛 掉给定区间上、整数中的那些合数和“1”，保留住其中的全部素数。 合数是被定义为两个以上素数之乘积，所以每个合数都存在着两个以上的素因子，那 么其中最小的那个，一定不大于该合数的平方根。因此[0,x ]上所有合数的最小素因子，一 定不大于 x 。筛掉了不大于 x 的所有素数p i 之整倍数，就筛掉了[0,x ]上的全部合数。 n 设不大于 x 的素数共有 个，从小到大排列，依次是： 、 、 、 p ( 2) p ( 3) p ( 5) 1 2 3 p 4 ( 7) …p i …p n 。传统筛法为了保留住包括p 1 、p 2 …p i …p n 在内的[0,x ] 上之全部素 n 数， 层p i 筛网都从 2p i 点起始进行筛除。即从2p i 点起，每隔p i 个整数就筛掉一个。其 筛法模型如例图（1）所示，其中的这三层筛网依次从 4、6、10 这三个点起始。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 例图（1）：仅用p 1 、p 2 、p 3 筛网筛除的传统筛法模型示意图 更细致分析和观察可知，每个p i 筛网的有效筛除点，实际是从p 2 点开始的，这是因为 i p 2 点之前p i 各筛点上的合数，其最小素因子只能是小于p i 的p j ，该合数一定是被p j 筛过 i 的p i 之重复筛点，无需再用p i 筛除。所以各p i 的起始筛点推后到p 2 点，其筛除效果未变。 i 因此上例中的三个起始点可推后到 4、9、25，使其筛法模型更简单，如例图（2）所示： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 2 n 至此，再单独删掉既非素数也非合数的“1”，传统筛法用 层p i 筛网就筛掉了小于p n+1 的全部合数和删掉了 “1”，存留下来的、是小于p 2+ 的全部素数。 n 1 由于素数越小越稠密、越大越稀疏，所以，以保留全部素数为目的的传统筛法模型，