给出一整数n，写一个时间复杂度为O(sqrt(n))的分解质因数的代码

### 回答1：

我们可以使用质因数分解的算法来实现O(sqrt(n))的时间复杂度，代码如下：int n; // 输入的整数
vector<int> factors; // 存放因子for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
factors.push_back(i);
n /= i;
}
}if (n > 1)
factors.push_back(n);

### 回答2：
要将一个整数n进行质因数分解，即将n进行因数分解成为质数的乘积，可以采用试除法：

首先，我们从最小的质数2开始，依次判断n是否能被2整除，如果可以，则将2作为一个因子，并将n除以2的结果作为新的n；
接着，我们判断n是否能被3整除，如果可以，则将3作为一个因子，并将n除以3的结果作为新的n；
依次类推，我们判断n是否能被5、7、11、13、17等质数整除，直到试除的数i小于等于sqrt(n)为止。

下面是时间复杂度为O(sqrt(n))的分解质因数的代码：

import math

def primeFactorization(n):
    factors = []
    i = 2
    while i <= math.sqrt(n):
        if n % i == 0:
            factors.append(i)
            n /= i
        else:
            i += 1
    if n > 1:
        factors.append(int(n))
    return factors

n = int(input("请输入一个整数n："))
result = primeFactorization(n)
print("整数n的质因数分解结果为：", result)

代码中使用了math.sqrt(n)来计算n的平方根，防止i超过sqrt(n)。时间复杂度为O(sqrt(n))的原因是，在最坏情况下，例如n为一个质数，并且大于sqrt(n)，需要试除到sqrt(n)才能确定n是一个质数。

例如，当n=12时，其质因数分解结果为[2, 2, 3]；
当n=25时，其质因数分解结果为[5, 5]；
当n=43时，其质因数分解结果为[43]。

### 回答3：
分解质因数是将一个整数n表示为质因数的乘积，其中质因数是指只能被1和它本身整除的数。

下面是一个时间复杂度为O(sqrt(n))的分解质因数的代码实现：

import math

def factorize(n):
    factors = []
    # 如果n能被2整除，直接将2加入质因数列表，并将n除以2
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    
    # 在范围[3, sqrt(n)]内循环，步长为2，跳过偶数
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        # 如果n能被i整除，将i加入质因数列表，并将n除以i
        while n % i == 0:
            factors.append(i)
            n //= i
    
    # 如果n大于2（即n是一个质数），直接将n加入质因数列表
    if n > 2:
        factors.append(n)
    
    return factors

# 测试代码
n = 36
print(factorize(n))  # 输出: [2, 2, 3, 3]

以上代码首先判断n能否被2整除，如果可以，将2加入质因数列表，并将n除以2。接下来，从3开始，在范围[3, sqrt(n)]内循环，步长为2，跳过偶数。对于每个循环中的i，如果n能被i整除，将i加入质因数列表，并将n除以i。最后，如果n大于2，将n加入质因数列表。

该代码的时间复杂度为O(sqrt(n))，因为在循环中，每次只检查一个质数是否能整除n，而循环次数为sqrt(n)次。因此，该代码的时间复杂度为O(sqrt(n))。