给定正整数n ( 2 <n <231 — 1),返回其质因数分解结果。 输入参数: n:待分解的正整数。 返回值: 一个二维数组,包含每个质因数以及其出现的次数。写出解题Java代码
时间: 2024-02-15 13:04:56 浏览: 28
以下是Java代码实现:
```java
public int[][] primeFactorization(long n) {
List<Integer> factors = new ArrayList<>();
for (int i = 2; i <= Math.sqrt(n); i++) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
if (n > 1) {
factors.add((int) n);
}
int[][] result = new int[factors.size()][2];
int index = 0;
int count = 1;
int pre = factors.get(0);
for (int i = 1; i < factors.size(); i++) {
if (factors.get(i) == pre) {
count++;
} else {
result[index][0] = pre;
result[index][1] = count;
index++;
count = 1;
pre = factors.get(i);
}
}
result[index][0] = pre;
result[index][1] = count;
return Arrays.copyOf(result, index + 1);
}
```
该方法使用质因数分解的方法,从2开始枚举所有可能的质因数,每次尝试将n除以该质因数,如果可以整除,则说明该质因数是n的因数,将其加入到因数列表中,并将n更新为除以该质因数的结果。重复这个过程,直到n变为1,此时所有的因数都已找到。最后,统计每个质因数出现的次数,将结果存储在一个二维数组中返回。
时间复杂度为O(sqrt(n)),其中sqrt(n)为n的平方根。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)