我要招人

去企业版

首页 > 试题广场 >

分解质因数

[编程题]分解质因数

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

质数又称素数。一个大于 $1$ 的自然数，除了 $1$ 和它自身外，不能被其他自然数整除的数叫做质数，否则称为合数。

请将一个正整数 $n$ 分解质因数，从小到大的顺序返回其质因子。

示例1

输入

输出

[2,2,5,5]

说明

100=2*2*5*5

示例2

输入

输出

[17]

备注:

算法知识视频讲解

阿英要上岸

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型一维数组
     */
    public int[] primeFactorization (int n) {
        // write code here
        List<Integer> res = new ArrayList<>();
        int i=2;
        while(n>1){
            if(n%i==0){
                res.add(i);
                n = n/i;
            }else{
                i=i+1;
            }
        }
         
        int len = res.size();
        int[] result = new int[len];
        for(int j=0; j<len; j++){
            result[j] = res.get(j);
        }
        return result;
    }
}

发表于 2022-06-14 19:56:38 回复(0)

C/C++

cwq777

class Solution {
public:
vector<int> primeFactorization(int n) {
vector<int> a;
for(int i=2;i<n;i++)
{
while(n!=i)
{
if(n%i==0)
{
a.push_back(i);
n=n/i;
}
else
break;

}

}
a.push_back(n);
return a;
}
};

发表于 2021-09-08 18:44:18 回复(0)

Python

忧伤的灰太狼摆烂了

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型一维数组
#
class Solution:
    def primeFactorization(self, n):
        res = []
        i = 2
        while n > 1:
            while n % i == 0:
                res.append(i)
                n = n // i
            i += 1
        return res

发表于 2024-12-24 15:48:14 回复(0)

C/C++

牛客600395775号

bool isprime(int n) {
    if (n == 1) {
        return false;
    }
    if (n == 2) {
        return true;
    }
    for (int i = 2; i <= n / 2; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}
int* primeFactorization(int n, int* returnSize ) {
    int count = 0;
    
    while (n > 1) {
        for(int i = 2;i <= n;i++){
        if (n % i == 0 && isprime(i)) {
            returnSize[count++] = i;
            n = n / i;
            break;
        }
        }
    }

    return returnSize;
}

DEVC 能跑出来，这里不知道为甚么是错的

发表于 2023-03-24 13:02:35 回复(0)

阿米诺斯

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型一维数组
*/
function primeFactorization(n){
let fs=[];
if(isPrimeNum(n)){
return [n];
}
for(let i=2;i<=n;i++){
if(isPrimeNum(i)){
while(n%i===0){
fs.push(i);
n/=i;
}
}
}

return fs;
}

function isPrimeNum(n) {
let sq = Math.floor(Math.sqrt(n));
for (let i = 2; i <= sq; i++) {
if (n % i == 0) return false;
}
return true;
}
module.exports = {
primeFactorization: primeFactorization
};

发表于 2022-06-29 21:21:59 回复(1)

把你吃的给我分点

class Solution:
    def primeFactorization(self , n ):
        # write code here
        ans = []
        i = 2
        while n > 1:
            if n % i == 0:
                ans.append(i)
                n //= i
            else:
                i += 1
        return ans

强势飘过

发表于 2022-06-03 16:06:32 回复(0)

soyyazzz

vector<int> primeFactorization(int n) {
    vector<int> a;
    for (int i = 2; i < n; ++i) {
        while (i != n && n % i == 0) {
            a.push_back(i);
            n /= i;
        }
    }
    a.push_back(n);
    return a;
}

稍微修改了一下楼上有位兄弟的写法

编辑于 2021-09-20 21:56:00 回复(0)

acechen15

class Solution:
    def primeFactorization(self , n ):
        # write code here
        import math
        i = 2
        max_num = math.sqrt(n)
        res = []
        while i <= max_num:
            if n % i == 0:
                res.append(i)
                n = n // i
            else:
                i += 1
        if n != 1:
            res.append(n)
        return res

发表于 2021-08-31 19:57:39 回复(0)

牛客155722426号

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型一维数组
*/
public int[] primeFactorization (int n) {
// write code here
List<Integer> a =new ArrayList();
for(int i = 2;i<=n;i++){
while( n%i ==0){
a.add(i);
n = n/i;
}
}
int[] b = a.stream().mapToInt(Integer::valueOf).toArray();
return b;
}
}

发表于 2021-08-25 18:41:05 回复(0)

Python

牛客782693764号

import math
class Solution:
def primeFactorization(self , n ):
res=list()
if n<=3:
res.append(n)
if n>=4:
x=2
while n>=x**2:
if n%x!=0:
x=x+1
if n%x==0:
res.append(x)
n=int(n/x)
res.append(n)
return res

发表于 2021-08-04 09:07:03 回复(0)