正整数分解质因数

Description

还记得什么是质因数吗？

质因数就是一个数的约数（b能整除a，b称为a的约数），并且是质数（又称素数）。

比如8=2×2×2，2就是8的质因数；

12=2×2×3，2和3就是12的质因数。

把一个式子以12=2×2×3的形式表示，叫做分解质因数。

分析：对n进行分解质因数，应先找到一个最小的质数i，然后按下述步骤完成：

1. 如果这个质数恰等于n，则说明分解质因数的过程已经结束，输出即可。
2. 如果n > i，但n能被i整除，则应打印出i的值，并用n除以i的商作为新的正整数，重复执行第一步。
3. 如果n不能被i整除，则用i+1作为i的值，重复执行第一步。

Input

输入示例：

10

50

90

Output

（输出请严格对照输出示例格式，不要包含空格等无关字符）输出示例：

2*5

2*5*5

2*3*3*5

Java解决方法

import java.util.Scanner;

public class Main {
    public static void solve1(int n) {
        for (int i = 2; i <= n; i++) {
            if (i == n) {
                System.out.print(i);
            }
            if (n > i && (n % i == 0)) {
                System.out.print(i + "*");
                solve1(n / i);
                break;
            }
        }
    }
    public static void main(String[] args)
    {
            Scanner sc = new Scanner(System.in);

            solve1(sc.nextInt());

    }
}

Python解决方法

• By - old_uncle

n=int(input())
m=n
def func(n):
    for i in range(2,n+1):
        if (n%i==0):
            print(i,end='')
            n/=i
            if n!=1:
                print('*',end='')
                return func(int(n))
func(m)

其他

• 如果您想发布自己的算法代码，欢迎到这里来和我们一起讨论！https://dodd.bingyishow.top/d/7--

版权属于：ic翼

本文链接：https://bingyishow.top/algorithm/59.html

您必须遵守 署名-非商业性使用-相同方式共享 CC BY-NC-SA 使用这篇文章