方法
使用素数筛（前期全部求出），但num>109就会内存不足。从2开始遍历每个数，计算是否为素数，再计算是否可以整除。小技巧
已求出的质数，存入数组保存，省去对这些数重复计算的时间。判断是否为质数，只需从 2 − a 2-\sqrt{a} 2−a 即可。 #include <time.h> // 判断是否为质数 int isPrime(int M){ for(int i=2;i<M;i++){ if(M%i==0){ return 0; } } return 1; } int main(){ clock_t start, end; start = clock(); int a = 0; //input cin >> a; int index = 2; int num = a; while(num!=1){ while(isPrime(index)!=1) index++; // 寻找质数 int cot=0; // 记录次方 while(num%index==0){ // 从num中除index num = num/index; cot++; } if(cot!=0){ cout << index << "^" << cot << endl; index=2; } index++; } end = clock(); double dur = (double)(end-start); printf("%f",(dur/CLOCKS_PER_SEC)); return 0; }