上周参加淘宝的校招面试,由于算是临时被派去的,除了基础的算法和数据结构,还有个编程题灵机一动 让大家 分解质因数

即类似 把 12 分解成 2_2_3来

基本上被我面到的都会问这个编程题.这题挺简单一般 10行代码就能搞定,但是要在短时间内,写的又好有严谨还是有难度了

基本上大部分都给出了 递归的解法:

void resolve(int num) {
    for (int i = 2; i <= num; i++) {
        if (num % i == 0) {
            cout << i << endl;
            resolve(num / i);
            break;
        }
    }
}

其中有一个妹纸给出了展开递归的解法,让我眼前一亮:

void resolve(int num) {
    while (num != 1) {
        for (int i = 2; i <= num; i++) {
            if (num % i == 0) {
                cout << i << endl;
                num /= i;
                break;
            }
        }
    }
}

最后还有一个妹子给出了算是比较接近最终的解法:

void resolve(int num) {
    int i = 2;
    while (num != 1) {
        if (num % i == 0) {
            cout << i << endl;
            num /= i;
        } else {
            i++;
        }
    }
}

当然分解质因数还是有更牛逼的Pollard Rho快速因数分解.但这不是一般人能在短时间内写得出来的.
看来妹纸编程水平也不错哦~