求100以内质数(素数)的算法梳理 | 您所在的位置:网站首页 › 一百以内所有素数的和 › 求100以内质数(素数)的算法梳理 |
以下程序都是围绕质数的2点定理来写的。 质数定理: 1、从2开始到自身的-1的数中找到一个能整除的(从2开始到自身开平方的数中找到一个能整除的)。 2、一个合数一定可以分解成几个质数的乘积,也就是说,一个数如果能被一个质数整除就是合数。(使用列表保存质数) 使用定理1的基本写法: (1) n = 100 for i in range(2, n): for j in range(2, i): if i % j == 0: break else: print(i, end=' ')这种基本写法效率不高,有2点可以改进的地方: 1、第一层循环的i取值时,因为偶数确定不是质数,所以排除偶数,使用range()函数排除偶数,range(3, n, 2)这样就减少了一半的数。 2、第二层循环j取值时,考虑从2开始到i开平方取值,同时也把偶数排除range(3, int(i**0.5)+1, 2)这样也可减少一半的数。2就是质数,单独打印。 (2) 改进(1): n = 100 print(2) for i in range(3, n, 2): for j in range(3, int(i**0.5)+1, 2): if i % j == 0: break else: print(i, end=' ')(3) 再(2)的基础上还有优化的点,发现第一层循环i取值时,当i>10时,5的倍数也可排除。 n = 100 print(2) for i in range(3, n, 2): if i > 10 and i % 5 == 0: continue for i in range(3, int(i**0.5)+1, 2): if i % j == 0: break else: print(i, end=' ')(4) 利用定理2,用列表保存上一次的运算结果。 n = 100 L = [2] for i in range(3, n, 2): for j in L: if i % j == 0: break else: L.append(i) print(L)此种写法的效率不高,第一层循环的i没必要与列表中的每一个元素取余,与从2开始到i的开平方处之间的数取余即可。 (5) 改进(4): n =100 L = [2] for i in range(3, n, 2): flag = False for j in L: if i % j == 0: flag = True break if j > int(i**0.5): break if not flag: L.append(i) print(L)第二层循环第二个判断处if j > int(i**0.5)程序运行时,每次判断i都会开平方,所以提到循环之外。 (6) 改进(5): n = 100 L = [2] for i in range(3, n, 2): flag = False num = int(x**0.5) for j in L: if i % j == 0: flag = True break if j > num: break if not flag: L.append(i) print(L) |
CopyRight 2018-2019 实验室设备网 版权所有 |