python练习题:求10万以内的质数

1、使用质数定义计算

#version1import datetime    #导入模块计算效率start = datetime.datetime.now()
count = 0
for x in range(2,100000):     #求指定范围内的质数
    for i in range(2,x):      #除以1和本身之外的数
        if x % i == 0:
            break
    else:
        #print(x)
        count += 1
delta = (datetime.datetime.now() - start).total_seconds()    #total_seconds()总秒数
print('count=',count,'delta=',delta)    #墙上的时间

#执行结果:
count= 9592 delta= 148.146291    #效率极差

2、优化1:经计算,临界值为开方值

#version2:优化

import datetime    #导入模块计算效率
start = datetime.datetime.now()
count = 0
for x in range(2,100000):
    for i in range(2,int(x ** 0.5 + 1)):   #优化1,经测试:临界值为开方值
        if x % i == 0:
            break
    else:
        #print(x)
        count += 1
delta = (datetime.datetime.now() - start).total_seconds()    #total_seconds()总秒数
print('count=',count,'delta=',delta)

#执行结果:
count= 9592 delta= 1.084154    #效率极大提高

3、优化2:大于2的偶数全是合数

#version3:优化+

import datetime    #导入模块计算效率
start = datetime.datetime.now()
count = 1
#print(2)    #从3开始,自己打印2
for x in range(3,100000,2):                   #优化2:从3开始的奇数
    #for i in range(3,int(x ** 0.5 + 1)):     #优化3:奇数不用和2取模
    for i in range(3, int(x ** 0.5) + 1,2):   #优化4:即也不用和偶数取模
        if x % i == 0:
            break
    else:
        #print(x)
        count += 1
delta = (datetime.datetime.now() - start).total_seconds()    #total_seconds()总秒数
print('count=',count,'delta=',delta)    #墙上的时间

#执行结果:
count= 9592 delta= 0.553471    #性能进一步提高

4、优化3:5的倍数全是合数,剔除5的倍数

#version4:优化++

import datetime    #导入模块计算效率
start = datetime.datetime.now()
count = 1
#print(2)    #从3开始,自己打印2
for x in range(3,100000,2):                   #优化2:从3开始的奇数
    if x > 10 and x % 5 == 0:
        continue                              #优化5:剔除5的倍数
    #for i in range(3,int(x ** 0.5 + 1)):     #优化3:奇数不用和2取模
    for i in range(3, int(x ** 0.5) + 1,2):   #优化4:即也不用和偶数取模
        if x % i == 0:
            break
    else:
        #print(x)
        count += 1
delta = (datetime.datetime.now() - start).total_seconds()    #total_seconds()总秒数
print('count=',count,'delta=',delta)    #墙上的时间

#执行结果:
count= 9592 delta= 0.493866

5、思考,总结,再优化:

质数:所有的质数除过2,都是奇数;

质数:临界值(开方值);

质数:质数*质数肯定不是质数,给定列表存放已知质数,使用该列表值进行判断,在该值的基础上锁定临界值;

孪生质数:大于3的质数只有6N-1和6N+1两种形式,如果6N-1和6N+1都是素数,成为孪生素数(效率也挺高)

import datetime
n = 100000
count = 2
primenumber = [3]
start = datetime.datetime.now()
for i in range(5,n + 1,2):
    flag = False
    x = int(i ** 0.5)
    for j in primenumber:
        if j > x:
            flag = True
            break
        if i % j == 0:
            flag = False
            break
    if flag:
        count += 1
        #print(i)
        primenumber.append(i)
end = (datetime.datetime.now() - start).total_seconds()
print("count=",count,'  ',"time=",end)

#执行结果:
count= 9592    time= 0.449377
import datetime
n = 100000
count = 3
primenumbers = [3,5]
start = datetime.datetime.now()
x = 7
step = 4
while x < n:
    flag = False
    j = int(x ** 0.5)
    if x % 5 != 0:
        for i in primenumbers:
            if i > j:
                flag = True
                break
            if x % i == 0:
                flag = False
                break
        if flag:
            count += 1
            primenumbers.append(x)
    x += step
    step = 4 if step == 2 else 2

end = (datetime.datetime.now() - start).total_seconds()
print("count=",count,'  ',"time=",end)

#执行结果:
count= 9592    time= 0.380034

6、质数的应用:

应用在密码学领域,都要使用大素数

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:python练习题:求10万以内的质数 - Python技术站

(0)
上一篇 2023年4月2日
下一篇 2023年4月2日

相关文章

  • Python中模块的四种方式

    一、什么是模块? 模块是一系列功能的集合体,而函数是某一个功能的集合体,因此模块可以看成是一堆函数的集合体。一个py文件内部就可以放一堆函数,因此一个py文件就可以看成一个模块。如果这个py文件的文件名为module.py,模块名则是module。 二、模块的四种形式 在Python中,总共有以下四种形式的模块: 自定义模块:如果你自己写一个py文件,在文件…

    Python开发 2023年3月31日
    00
  • python学习:获取指定目录下所有文件名os.walk和os.listdir

    1.os.walk 返回指定路径下所有文件和子文件夹中所有文件列表 其中文件夹下路径如下: import os def file_name_walk(file_dir): for root, dirs, files in os.walk(file_dir): print(“root”, root) # 当前目录路径 print(“dirs”, dirs) #…

    Python开发 2023年4月2日
    00
  • Python教程:类的继承,什么是继承

    一、什么是继承 继承是一种新建类的方式,新建的类称为子类,被继承的类称为父类 继承的特性是:子类会遗传父类的属性 继承是类与类之间的关系 二、为什么用继承 使用继承可以减少代码的冗余 三、对象的继承 Python中支持一个类同时继承多个父类 class Parent1: pass class Parent2: pass class Sub1(Parent1,…

    Python开发 2023年3月31日
    00
  • Python教程:读取文件有三种方法:(read、readline、readlines)详细用法

    python3中,读取文件有三种方法:read()、readline()、readlines()。 此三种方法,均支持接收一个变量,用于限制每次读取的数据量,但是,通常不会使用。 本文的目的:分析、总结上述三种读取方式的使用方法及特点。 一、read方法 特点:读取整个文件,将文件内容放到一个字符串变量中。 缺点:如果文件非常大,尤其是大于内存时,无法使用r…

    Python开发 2023年4月2日
    00
  • Python教程:IO

    在磁盘上读写文件的功能都是由操作系统提供的,现代操作系统不允许普通的程序直接操作磁盘,所以,读写文件就是请求操作系统打开一个文件对象(通常称为文件描述符),然后,通过操作系统提供的接口从这个文件对象中读取数据(读文件),或者把数据写入这个文件对象(写文件)。 1.读文件 要以读文件的模式打开一个文件对象,使用Python内置的open()函数,传入文件名和标…

    Python开发 2023年3月31日
    00
  • Python深浅拷贝的理解

    1.拷贝 拷贝实际上其实就是在赋值,比如我们有一个列表L1,定义另一个列表L2引用列表L1,实际上就是在拷贝列表L1的值,由于由于L1列表是可变的数据类型,所以当L1的值变的时候,L2的值也是在跟着变的.那其实就算L1内的是不可变的数据类型,L1的内容变化,L2的内容也一样会随之变化的 # # 拷贝(赋值) # Python学习交流QQ群:153708845…

    Python开发 2023年3月31日
    00
  • python教程:shutil高级文件操作

    1、shutil高级文件操作模块 shutil模块提供了大量的文件的高级操作。特别针对文件拷贝和删除,主要功能为目录和文件操作以及压缩操作。对单个文件的操作也可参见os模块。 2、shutil模块的拷贝方法 >>> import shutil >>> shutil.chown(‘test.txt’,user=’mysql’…

    Python开发 2023年3月31日
    00
  • Python条件语句和循环语句简单使用方法

    1.Python条件语句 Python条件语句是通过一条或多条语句的执行结果(True或者False)来决定执行的代码块。 可以通过下图来简单了解条件语句的执行过程:Python程序语言指定任何非0和非空(null)值为true,0 或者 null为false。 Python 编程中 if 语句用于控制程序的执行,基本形式为: if 判断条件: 执行语句………

    Python开发 2023年4月2日
    00
合作推广
合作推广
分享本页
返回顶部