Java-java程序设计 求素数的优化方案

Answer 1

循环判断会不会是最快的

Answer 2

很久没写Java了，交流一个思路吧。基本上，大多数2，3，5的倍数可以直接过滤，难点在于素数积的那些合数比如判断11413 = 101 * 113
1. 偶数
2 * n: x & 1 == 0
2. 5整除 (尾数0被偶数过滤)
5 * n: x % 10 == 5
3. 3整除
3 * n: x % 3 == 0
以上没有难度容易判断，剩下就是重点部分。
单纯步长加1循环性能会随数字范围增大而严重下降，这里先提一个概念：孪生素数。可以查一下新闻，好像前段时间一个华裔数学家给出了证明：素数往往相伴而生，间隔为2，比如11-13、41-43、101-103……另外有个证明，素数之间的间隔为6，比如11-17、41-47，可以在网上搜到该论文。第三，合数如果有最大质数因子，不会大于其平方根。至此，基于现有的前提条件可以优化循环过程。下面是python的一段代码，会Java基本能读懂

maxV = math.floor(math.sqrt(srcNum)) + 1

if maxV < 7:
return True

step = 5

while maxV >= step:
if srcNum % step and srcNum % (step + 2):
step = step + 6
else:
return False