假设已有一个算法Prime(n)可用于测试整数n是否为一个素数，另外还有一个算法Split(n)可以实现对合数n的因子分割。试利用这两个算法设计一个对给定整数n进行因子分解的算法。
import math def Prime(n): m = math.floor(math.sqrt(n)) for i in range(2,m+1): if n % i== 0: return False return True #因子分割的确定性算法 def Split(n): k = math.floor(math.sqrt(n)) for i in range(2,k+1): if (n % i == 0): return i return 1 def fact(n): if(Prime(n)):#如果n是素数，直接返回n print(n) else: i=Split(n)#分解n的一个因子i if(i>1):#如果i 是非平凡因子，对i进行因子分割 fact(i) if(n>i):#对n的另外一个非平凡因子进行因子分割 fact(n//i)
举一反三
内容
- 0
算法设计题(5)设二维数组a[1..m,1..n]含有m*n个整数。1写一个算法判断a中所有元素是否互不相同?输出相关信息(yes/no);2试分析算法的时间复杂度。
- 1
对一个具有n个数据元素的有序表采用折半查找算法实现，查找的算法时间复杂度是（ ）。 A: O(1) B: O(logn) C: O(n) D: O(n^2)
- 2
对一个生成n个元素的所有排列对象的算法,其平凡下界是n!<br/>() A: 正确 B: 错误
- 3
算法可以有 0~n ( n 为正整数 ) 个输入，有 (<br/>) 个输出。 A: 0~n B: 0 C: 1~n D: 1
- 4
一个无序文件中的n个记录采用置换-选择算法产生m个有序段，则m和n的关系是（）。