[Python知识库]关于求素数为什么只用求到平方根，以及求素数复杂度更低的想法、附python代码

求素数为什么只用求到平方根

如果一个数可以拆分为两个因数,那么这两个因数必然有一个因数小于此数的平方根,有一个因数大于此数的平方根。
当一个数从2开始，遍历到它的平方根还没有找到一个因数的，就一定是素数。

如果$x$可以被分解为$a\times b$，即：
$$a\times b=x$$
令两边同时除以($b\times x$)，有：
$$\frac{a}{\sqrt{x}}=\frac{\sqrt{x}}{b}$$
若$a<\sqrt{x}$ ，则：$\sqrt{x}<b$
所以说：
两个因数必然有一个因数小于此数的平方根,有一个因数大于此数的平方根。

求素数复杂度更低的idea

可以先判断这个数是否可以被2整除,
如果不可以，再进行遍历，遍历时从3开始，设置step = 2
遍历的终点就是它的平方根。

代码

import math
def print_is_prime(number,T):  #输出字符串情况
    if T == 1:
        print(number,"is a prime")
    else:
        print(number,"is not a prime")
def is_prime(number):
    if number in [2,3,5,7]:   #简单的可以直接判断，不必进入下面循环
        return 1
    if number%2 ==0:
        return 0
    for i in range(3,int(math.sqrt(number))+1,2):
        if number%i == 0:
            return 0
            break
        else:
            continue
    return 1