题解 | #质数因子#

#include <iostream>
#include <memory.h>
#include <math.h>
using namespace std;

void GetProton() {
    int N;
    int proton[32] = { 0 };
    int tmp;
    int k = 0;

    //cout << "请输入一个正整数:" << endl;
    cin >> N;
    int i = 2;
    tmp = N;
    //memset(proton, 0, sizeof(proton));
    do {
        if (tmp % i == 0) {
            proton[k++] = i;
            tmp = tmp / i;
        } else {
            i++;
        }
    } while (i <= sqrt(N));

    //没有质数因子，说明它自身是个质数.
    if (k == 0 || (proton[k] != tmp && tmp > sqrt(N)))
	{
		proton[k++] = tmp;
	}

    //cout << N << "的质数因子是:" << endl;
    for (i = 0; i < k; i++) {
        cout << proton[i] << " ";
    }

    cout << endl;
    //cout << "请输入一个正整数:" << endl;
}

int main() {
    GetProton();
}
// 64 位输出请用 printf("%lld")

用sqrt(N)作为边界时，需要把最后一个整除后的结果tmp，也作为质数因子保存。这个数字有可能大于sqrt(N)。