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

tysh670407

一种不用判断素数筛选素数的方法
田永胜
（内蒙古自治区 吉兰泰 750333）
摘要：本文给出了一种不用判断素数筛选素数的方法及特点。
关键词： 判断素数；筛选素数；数列；互乘
中图分类号：O156.1

现在人们使用的筛法，是由古希腊数学家埃拉托色尼所提出的一种简单检定素数的方法。要筛出小于n的素数，先找出√n以内的素数。然后用√n以内的素数，去筛√n到n的素数。
这种方法对于n位数较小的情况来说，比如2到10位数字，比较容易，对于数字位数较大的情况，比如20到100位，则比较费时。那么，有没有一种方法不用判断素数就可以筛选素数呢？下面，我们就进行这方面的研究。
因为1既不是素数，也不是合数，不做研究，剩余的自然数从2开始进行排列，一直到9，共8个数列，如表1所示：



表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，5]：
在数列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，30]时的值为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列……等等。
这种方法既可以用于筛选素数，也可以用于分解合数。既可以用于筛选某一个数列上的所有素数，也可以筛选数列上某一区间的素数。

tysh670407

请会编程的网友，测试一下这种方法看对不对。