easy-algorithm-interview-and-practice/mathcasebycase/判断一个数是否为质数.md

1.质数的定义

只要有小学毕业证的同学都知道质数是什么鬼。因为本人没有小学毕业证，特意记录一下质数的定义：
对于大于1的数，如果除了1和它本身，它不能再被其它正整数整除，那么我们说它是一个质数。

2.判断是否为质数

import math

def isPrime(n):
    if n == 1:
        return False
    elif n < 4:
        return True
    else:
        sqrtNum = int(math.sqrt(n))
        //注意range的右边是开区间，所以要加1
        for i in range(2,sqrtNum+1):
            if n % i == 0:
                print "%d is not a prime number!" %n
        print "%d is a prime number! " %n

比较简单的版本，从2开始一直到n的均方根，如果都除不尽，那么n为质数。

3.优化版

def isPrime2(n):
    if n == 1:
        print "%d is not a prime number!" %n
        return False
    if n == 2 or n == 3:
        print "%d is a prime number!" %n
        return True
    if(n % 2 == 0)://先判断是否为偶数，若偶数就直接结束程序 
        return False 
    //从3开始，到n的算术平方根结束，步进为2 
    for i in range(3,int(math.sqrt(n))+1,2):
        if(n % i == 0):
            print "%d is not a prime number!" %n
            return False
    print "%d is a prime number!" %n
    return True

首先如果是偶数，直接返回；然后从3开始，步长为2，一直到n的算术平方根为止，都除不尽则为偶数。

4.判断一个数是否为质数，为什么除到其平方根就可以了

因为如果一个数不是素数是合数，
那么一定可以由两个自然数相乘得到，
其中一个大于或等于它的平方根，一个小于或等于它的平方根。并且成对出现。

如果要继续优化算法，请参考以下内容：
https://joezou.wordpress.com/2009/05/13/%E6%88%91%E4%B8%8E%E7%B4%A0%E6%95%B0/amp/