python输出2~100之间的素数 |
您所在的位置：网站首页 › 输出1到2000内所有的素数 › python输出2~100之间的素数 |
python输出2~100之间的素数
|
素数：素数又称质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。如 2、3、7、11 .... 思路：两个循环控制一个判断搞定(*^▽^*) 外循环 i ：遍历2~100，并定义一个初始值一直为True的标签flag。 内循环 j ：遍历小于 i 的数并被 i 取模，如果取模为0则表示是可以被其他数整除的数，那么 判定不是素数，flag就赋值为False，跳出内循环。 判断： 跳出内循环，flag还为True说明 i 为素数。
只想交作业的同学就可以结束了，想受表扬的同学咱们继续！ 优化处理（了解）本题取值范围较小，下面将本题的100改为100000并计算运行时间 from time import time start_time = time() count = 0 for i in range(2,100001): flag = True # 定义一个标签，判别是否是素数 for j in range(2,i): if i % j == 0: flag = False # 取模等于0就不是一个素数，flag变为False,跳出内循环 break if flag == True: # 跳出外循环，flag还为True则 i 数为素数 count += 1 print("1-100000以内一共有%d个素数"%count) end_time = time() run_time = (end_time - start_time) print("\n运行时间为:%d秒"%run_time)运行结果为80秒
直接取 j 中间值的左边循环，右边省去。假设检测11是不是一个素数，就去这个数的中间值5，5右边的数相除一定不为整数，如 11 / 6 = 1.83 ......11 / 10 = 1.1相除一定为一点几，草图理解如下
优化1代码如下 from time import time start_time = time() count = 0 for i in range(2,100001): flag = True # 定义一个标签，判别是否是素数 for j in range(2,int(i/2)): if i % j == 0: flag = False # 取模等于0就不是一个素数，flag变为False,跳出内循环 break if flag == True: # 跳出外循环，flag还为True则 i 数为素数 count += 1 print("1-100000以内一共有%d个素数"%count) end_time = time() run_time = (end_time - start_time) print("\n运行时间为:%d秒"%run_time)运行结果为35秒，比优化前快 80-35=45 秒
取 j 的 平方根值的左边循环，平方根左边的数在右边一定有个对应值，两个对应值相乘结果为100000，草图理解如下： 优化二代码如下 from time import time start_time = time() count = 0 for i in range(2,100001): flag = True # 定义一个标签，判别是否是素数 for j in range(2,int(i**0.5+1)): # 取到开方数 if i % j == 0: flag = False # 取模等于0就不是一个素数，flag变为False,跳出内循环 break if flag == True: # 跳出外循环，flag还为True则 i 数为素数 count += 1 print("1-100000以内一共有%d个素数"%count) end_time = time() run_time = (end_time - start_time) print("\n运行时间为:%d秒"%run_time)运行结果，0秒
|
【本文地址】
今日新闻 |
推荐新闻 |