一种不用判断素数筛选素数的方法

tysh670407

一种不用判断素数筛选素数的方法

田永胜

（内蒙古自治区 吉兰泰 750333）

摘要：本文给出了一种不用判断素数筛选素数的方法及特点。

关键词： 判断素数；筛选素数；数列；互乘

中图分类号：O156.1

现在人们使用的筛法，是由古希腊数学家埃拉托色尼所提出的一种简单检定素数的方法。要筛出小于n的素数，先找出√n以内的素数。然后用√n以内的素数，去筛√n到n的素数。

这种方法对于n位数较小的情况来说，比如2到10位数字，比较容易，对于数字位数较大的情况，比如20到100位，则比较费时。那么，有没有一种方法不用判断素数就可以筛选素数呢？下面，我们就进行这方面的研究。

因为1既不是素数，也不是合数，不做研究，剩余的自然数从2开始进行排列，一直到9，共8个数列，如表1所示：

n	8n+2	8n+3	8n+4	8n+5	8n+6	8n+7	8n+8	8n+9
0	2	3	4	5	6	7	8	9
1	10	11	12	13	14	15	16	17
2	18	19	20	21	22	23	24	25
3	26	27	28	29	30	31	32	33
4	34	35	36	37	38	39	40	41
5	42	43	44	45	46	47	48	49
6	50	51	52	53	54	55	56	57
7	58	59	60	61	62	63	64	65
8	66	67	68	69	70	71	72	73
9	74	75	76	77	78	79	80	81

表1 自然数排列表

从表1可以看出数列8n+2，8n+4，8n+6，8n+8，均为偶数列，数列8n+3，8n+5，8n+7，8n+9，均为奇数列，而素数就在分布这4个数列上。

我们先看这四个奇数列上的数有什么特点：

首先，把四个奇数列上的数互乘或自乘，

3×9=27，除8余3，在数列8n+3上，同样，5×7=35，除8余3，也在数列8n+3上；

3×7=21，除8余5，在数列8n+5上，同样，5×9=45，除8余5，也在数列8n+5上；

3×5=15，除8余7，在数列8n+7上，同样，7×9=3，除8余7，也在数列8n+7上；

3×3=9，除8余1，在数列8n+9上，同样，5×5=25，除8余1，在数列8n+9上；7×7=49，除8余1，在数列8n+9上，同样，9×9=81，除8余1，也在数列8n+9上；

四个奇数列上的数互乘或自乘与筛选素数有什么关系呢？

我们先拿数列上的几个数来研究一下，例如n取[0，：

在数列8n+3上，当n=0，1，2，3，4，5时，数列为3，11，19，27，35，43。当x，y取0时，（8x+3）和（8y+9）的乘积27和（8x+5）和（8y+7）的乘积35，也在这个数列上，筛去这两个数，剩余的就是素数3，11，19，43。

在数列8n+5上，当n=0，1，2，3，4，5时，数列为5，13，21，29，37，45，当x，y取0时，（8x+3）和（8y+7）的乘积21和（8x+5）和（8y+9）的乘积45，也在这个数列上，筛去这两个数，剩余的就是素数5，13，29，37。

在数列8n+7上，当n=0，1，2，3，4，5时，数列为7，15，23，31，39，47，当x，y取0时，（8x+3）和（8y+5）的乘积15和39，也在这个数列上，筛去这两个数，剩余的就是素数7，23，31，47。

在数列8n+9上，当n=0，1，2，3，4，5时，数列为9，17，25，33，41，49，当x，y取0时，（8x+3）和（8y+3）的乘积9和33，（8x+5）和（8y+5）的乘积25，（8x+7）和（8y+7）的乘积49，也在这个数列上，筛去这4个数，剩余的就是素数17，41。

经过研究发现，数列（8n+3）与数列（8n+9）上的数相乘及数列（8x+5）与数列（8y+7）上的数相乘都在数列（8n+3）上，只要筛去（8x+3）（8y+9）和（8x+5）（8y+7）这些数，剩余的数都是素数。（n，x，y=0，1，2，3…）

同理，在数列8n+5上，只要筛去（8x+3）（8y+7）和（8x+5）（8y+9）这些数，剩余的数都是素数。（n，x，y=0，1，2，3…）

同理，在数列8n+7上，只要筛去（8x+3）（8y+5）和（8x+7）（8y+9）这些数，剩余的数都是素数。（n，x，y=0，1，2，3…）

同理，在数列8n+9上，只要筛去（8x+3）（8y+3）和（8x+5）（8y+5）（8x+7）（8y+7）和（8x+9）（8y+9）这些数，剩余的数都是素数。（n，x，y=0，1，2，3…）

上述筛法中，只要筛掉数列中的合数，剩余的就是素数，而这些合数是这4个奇数列的互乘或自乘，不需要去判断一个数是不是素数，因此比埃拉托色尼筛法快很多。

这种筛法既可以筛选2到某一个数n之间的素数，也可以筛选某一区间内的素数，比如在数列8n+7上，寻找 n从10到30之间的素数，只需筛去满足不等式

247≥（8x+3）（8y+5）≥87和247≥（8x+7）（8y+9）≥87  

上的数即可（筛选过程会有满足条件的重复数出现，计数时只记1次），剩余的大于87，小于247的数就是素数。

在数列8n+7上，n取[10，时的值为87，95，103，111，119，127，135，143，151，159，167，175，183，191，199，207，215，223，231，239，247。

满足不等式 247≥（8x+3）（8y+5）≥87 的数有87，95，111，135，143，159，183，207，215，231，247。

满足不等式 247≥（8x+7）（8y+9）≥87 的数有 119，135，175，231。

剩余的数 103，127，151，191，199，223，239 就是素数。

这种方法可以计算出数列在某个区间的素数个数。即将区间的数字个数减去满足不等式的个数，余数就是素数个数。

上面研究的是8个数列排列的情况（8n+2到9），也可以推广到16个数列排列的情况（16n+2到17），32个数列排列的情况（32n+2到33），以及64列，128列，256列，512列，1024列……等等。

这种方法既可以用于筛选素数，也可以用于分解合数。既可以用于筛选某一个数列上的所有素数，也可以筛选数列上某一区间的素数。

: w! x7 M( o/ ^1 L- d+ V5 b

tysh670407

请会编程的网友测试一下，看这种方法对不对。
5 |/ n6 u1 x, G6 j; B8 M. _

武汉方程

学习了，很新颖。谢谢。
/ L- f4 P! c( [* ?- G5 L/ h