目录
# Python
# 素数最强优化:
任何一个自然数,总可以表示成以下六种形式之一:6n,6n+1,6n+2,6n+3,6n+4,6n+5(n=0,1,2...)我们可以发现,除了2和3,只有形如6n+1和6n+5的数有可能是质数。且形如6n+1和6n+5的数如果不是质数,它们的因数也会含有形如6n+1或者6n+5的数,因此可以得到如下算法:
def is_prime4(x):
if (x == 2) or (x == 3):
return True
if (x % 6 != 1) and (x % 6 != 5):
return False
for i in range(5, int(x ** 0.5) + 1, 6):
if (x % i == 0) or (x % (i + 2) == 0):
return False
return True