素数

又称质数（Prime number）。指在正整数中，除了1和该数自身外，无法被其他数整除的数。

方法1 （ $O (n)$ ）

从2开始寻找，直到 $n ? 1$ 。如果没有找到可以整除这个数的数，那么这个数是素数。

def isPrime(n):
    for k in range(2,n):
        if n%k ==0:
            return False
    return True

方法2（ $O(\sqrt{n})$ ）

从2开始寻找，直到 $i n t (s q r t (n)) + 1$ 。如果没有找到可以整除这个数的数，那么这个数是素数。

def isPrime(n):
    for k in range(2,int(n**0.5)+1):
        if n%k ==0:
            return False
    return True

方法3（略小于 $O(\sqrt{n})$ ）

素数除了2，首先不能是偶数。再判断其是否能被某一奇数整除。

def isPrime(n):
	if n==2 or n==3:
		return True
    if n%2==0: # 2,3
        return False
    for k in range(3,int(n**0.5)+1,2): # 判断该数能否被奇数整除。
        if n%k==0:# 判断左边和右边是否可以被n整除。
            return False
    return True

方法4（远小于 $O(\sqrt{n})$ ）

在大于等于5的正整数中，素数一定是出现在6的倍数的左右两边（其中一边或两边都是）。同时，出现在6的倍数的两边的数是可以被素数整除。

def isPrime(n):
    if n <=3 and n >1: # 2,3
        return True
    if n%6 != 1 and n%6!=5: # 判断是否在6的倍数的两边。
    						#如果不在，则一定不是素数。
    						#如果在，则需要进一步判断 (此时该数已经不是偶数)。
        return False
    for k in range(5,int(n**0.5)+1,6): # 判断该数能否被从5到sqrt(n)+1中的素数整除。
        if n%k==0 or n%(k+2)==0: # 判断左边和右边是否可以被n整除。
            return False
    return True