题解 | #分解质因数#

- 先判断质数，再判断因数

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型vector
     */
    vector<int> primeFactorization(int n) {
        vector<int>s;

        for(int i=2;i*i<=n;i++){
            bool isprime=true;
            for(int j=2;j*j<=i;j++){
                if(i%j==0)isprime=false;
                 break;
            }
            if(isprime){
                while(n%i==0){
                    s.push_back(i);
                    n=n/i;
                }
            }
        }
        if(n!=1)s.push_back(n);
    
    return s;
    }
};

直接判断因数 (因为若除的是合数，合数的质因数必然在之前已被除过，不可能整除了)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型vector
     */
    vector<int> primeFactorization(int n) {
        vector<int>s;

        for(int i=2;i*i<=n;i++){
                while(n%i==0){
                    s.push_back(i);
                    n=n/i;
                }
        }
        if(n!=1)s.push_back(n);
    return s;
    }
};