pyhton 查找一个数的所有因子 以及 判断一个数是否是质数 .

32324

pyhton 查找一个数的所有因子 以及 判断一个数是否是质数 两个小脚本
最近看到一个网站， 欧拉计划。挺好玩，都是一些算法题。这是本站：http://projecteuler.net/problems  这个是中文站：http://pe.spiritzhang.com/

下面贴两个小脚本，低端玩具

1.找出一个数的所有因子：


#encoding:utf-8
import math

def yinzi(n):
    list_yinzi = []
    if n <= 2:
        return list_yinzi
    for i in range(2, int(math.sqrt(n)) + 1):
        """
        为什么循环范围定在平方根呢？：因为一个数的因子是成对的，a=b*c。也就是说：找到一个因子b，肯定会找到相对应的另外一个因子c（a/b）。所以我们的工作量减少了一半。
        又有：一个因子变大，另一个因子必然要变小。假设b永远是小的那个，c是大的那个，那么b的最大值就是a的平方根。也就是b=c=(根号a)的时候。所以循环范围定在[1 , a的平方根+1]，+1的原因是为了能够取到a的平方根避免遗漏。
        """
        #如果找到了一个因子，那么把其相对应的另一个因子一同加入到因子列表中
        if n % i == 0:
            list_yinzi.extend([i, n/i])

    #此处的set为了去重，因为会出现两个相同的平方根的情况。所以去掉重复
    #sorted重排序是因为，因子都是成对成对找出来的，也就是说一次找到的两个因子肯定会有一大一小。这样把所以因子找完放在一起，大小排序就乱了
    return sorted(set(list_yinzi))



2.判断一个数是否是质数 ：


#encoding:utf-8
import math

def is_zhishu(n):
    if n <=1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        """循环范围同查找因子类似，由于因子是成对出现的，所以只需要循环到小于平方根的范围就好"""
        if n % i == 0:
            return False
    return True