Python3 找素数

发布时间:2019-09-27 07:13:18编辑:auto阅读(1671)

    脑袋一热,想看一下300以内的最大素数是多少,就写了一个。
    注意:对正整数n,如果用2到n的平方根之间的所有整数去除,均无法整除,则n为质数(素数)。

    # -*- coding:utf-8 -*-
    import math
    import time
    
    ss = []  #  放可能是素数的列表
    fss = []  # 放可能是非素数的列表
    result = []  # 最终结果
    x = 300
    
    print("start!" )
    start = time.clock()
    # 遍历所有小于X,大于2的数
    for xx in range(2, x+1):
        # 只要xx的数,不能被2至xx的平方根的所有数整除,就是素数
        for i in range(2, int(math.sqrt(xx)+1)):
            if (xx % i) != 0:
                i = i + 1
                # print("素数: ",xx)
                ss.append(xx)
            else:
                # print("非素数", xx)
                fss.append(xx)
    
    # 只要x中的数没有出现在非素数列表中,则它就是素数
    for j in range(2, x+1):
        if j not in fss:
            result.append(j)
    
    print("result: ", result)
    
    end = time.clock()
    times = ''.join("%f s" % (end - start))  # 看用时多久
    print("end!\n耗时:", times)

    结果:

    start!
    result:  [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]
    end! 
    耗时:0.002066 s

    百度百科里有一个比较简单:而且速度也快。

    # 判断是否为素数
    def is_prime(n):
        if n == 1:
            return False
        for i in range(2, int(math.sqrt(n)+1)):
            if n % i == 0:
                return False
        return True
    
    start = time.clock()
    print("start:" )
    for n in range(2, x+1):
        if is_prime(n) is True:
            result.append(n)
    print(result)
    end = time.clock()
    times = ''.join("%f s" % (end - start))
    print("end!\n耗时:", times)

    结果

    start:
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]
    end!
    耗时: 0.000434 s

关键字