专栏首页python3Python3 找素数

Python3 找素数

脑袋一热,想看一下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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如何在python中比较微秒时间差(mi

    用户2398817
  • Python之路(三)Python数据类

    布尔值只有True,False两种值,要么是True,要么是False,在Python中可以直接使用True,False来表示布尔值(需要注意大小写)。

    用户2398817
  • python3入门与进阶(二)

    如果字符串可以改变,那么可以使用索引值给字符串赋值"python"[0] = 'h' -----> 报错,会发现报错,是不行的。

    用户2398817
  • 测试面试题集-Python花式打印九九乘法口诀表

    面试的时候,面试官可能要求原地秀一段代码,比如小学生都必须会默写的九九乘法口诀表,有长方形格式、左下三角形格式、左上三角形格式、右上三角形格式、以及右下三角形格...

    ITester软件测试小栈
  • Python实现简单登陆验证(文件操作)

           1.用户名的验证,首先对存储用户名和密码的信息读取,然后再把输入的用户名和从文件中读取的用户名进行比对,如果比对成功则进行下一步的密码验证,如果没...

    用户2398817
  • python 中各种简单的代码写法

    range(sIndex,eIndex) :生成一个从sIndex到eIndex的数字序列

    用户2398817
  • 剑指 offer——面试题8求旋转数组的最小值

    题目:将一个非递减序列的某一处切一刀,再把前半段序列放到后半段序列的后面,这样组成的新序列叫做“旋转数组”。要求获取一个旋转数组的最小值。 这本质上是一个求最值...

    大闲人柴毛毛
  • CSS3 animation steps介绍

    steps()有一定的学习难度,总是搞不清楚,最主要就是start和end傻傻分不清楚。我这里自我挑战下,看看能不能说清楚。

    javascript.shop
  • 从头开始了解Transformer

    编者按:自2017年提出以来,Transformer在众多自然语言处理问题中取得了非常好的效果。它不但训练速度更快,而且更适合建模长距离依赖关系,因此大有取代循...

    AI科技评论
  • 冷思考:数据中台的迷失与前行

    这波由互联网巨头们带起来的中台热潮,看似偶然,其实必然。它让我们真正意识到数据形成资产化之后带来的巨大价值,以及企业与机构在未来的竞争中构建起数据资产体系和组织...

    大数据在线

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动