知识卡片
质因子可逐次约去
对大于1的整数,可先找最小质因子i,把它记录下来,再对n/i继续同类问题,直到剩余数本身为质数。原例2409依次约去3与11,剩73,得到质因子集合{3,11,73}。
把记录动作放在递归调用前,返回后无需再组合,因此这是尾递归描述。这里用集合P记录不同因子,不保留重复因子的重数;本节也没给找最小质因子的具体程序或处理0、1的规则,不补成完整高效分解API。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 质因子可逐次约去
原书出处 · 1 处
- · 查看原书依据
先确定它的最小质因子i并把它记录到集合P中,然后对整数n=n/i重复这个过程直到n本身成为质数为止,这就是终止条件。这个定义是尾递归的,因为在回归过程中不需要做任何处理,如图3-6所示。 图 3-6 以尾递归的方式计算整数2409的质因子 问:思考当执行递归函数时栈的使用情况,当递归过程的递推阶段永
参考来源
- 位置:《算法精解:C语言描述》第3章《问与答》(spine1196;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1164.html;u037-ch03-007)。
- 结论依据:37质因子问答与02687-02688公式/2409链,记录P及素数终止直接支撑步骤和集合语义;未执行因子搜索。
- 原始内容:先确定它的最小质因子i并把它记录到集合P中,然后对整数n=n/i重复这个过程直到n本身成为质数为止,这就是终止条件。这个定义是尾递归的,因为在回归过程中不需要做任何处理,如图3-6所示。 图 3-6 以尾递归的方式计算整数2409的质因子 问:思考当执行递归函数时栈的使用情况,当递归过程的递推阶段永