判断素数/质数的快速算法

质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个因数的数）。——via维基百科

朴素算法：

1.

def isprime(n):
	"""
        :type n:int
        :rtype:bool
        """
	if n==1:
		return False
	for i in range(2,n):
		if n%i==0:
			return False
	return True

2.

import math
def isPrime(n):
"""
        :type n:int
        :rtype:bool
        """
    if n == 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

 

埃氏筛法: 运算速度更快的判断素数算法。

可以知道除了2（2是素数）以外的其他偶数都不是素数，除了3（3是素数）以外其他能被3整除的数都不是素数。所以一个素数的整数倍都不是素数，可以利用这一点编写算法如下：

def isprime(n):
    """
        :type n:int
        :rtype:List[int]
        """
    s=[True for i in range(n+1)]#首先默认所有的数都是质数
    z=[]#存放质数
    for i in range(2,n+1):#1不是质数
        if s[i]:#判断是否为质数，如果没有被标记就是质数
            z.append(i)
            for j in range(i+i,n+1,i):#剔除倍数（如果是质数，质数的倍数一定不是质数）
                s[j]=False
    return z

算法参考：http://t.csdn.cn/s8wOY