首页 > 试题广场 >

分解因数

[编程题]分解因数

热度指数：9196 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

所谓因子分解，就是把给定的正整数a，分解成若干个素数的乘积，即 a = a1 × a2 × a3 × ... × an,并且 1 < a1 ≤ a2 ≤ a3 ≤ ... ≤ an。其中a1、a2、...、an均为素数。先给出一个整数a，请输出分解后的因子。

输入描述:

输入包含多组数据，每组数据包含一个正整数a（2≤a≤1000000）。

输出描述:

对应每组数据，以“a = a1 * a2 * a3...”的形式输出因式分解后的结果。

示例1

输入

10<br/>18

输出

10 = 2 * 5<br/>18 = 2 * 3 * 3

算法知识视频讲解

whoway

发表于 2020-08-30 08:28:47

解法 1）素数筛2）用递归写出能分解的最小的素数能拥递归的前提:预知了递归的层数不会太大原因：最小素数是2假设是六位数的数，全是由于2来组成的，也就是我们最大的递归层数由于2^10=1024粗略估计，那么2^20约等于1000000也就是说，最大递归不会超过20层。 AC代码 #include< 展开全文