C语言——质因子

### C语言中质因子分解的时间复杂度分析 对于C语言中的质因子分解，存在多种方法来实现这一目标。每种方法具有不同的时间复杂度。 #### 使用试除法进行质因子分解 一种常见的策略是从最小的素数开始尝试去除给定整数\( n \)，直到无法再除去为止。这种方法适用于较小数值范围内的输入数据。当处理较大数值时，则可以采用更高效的算法如Pollard Rho快速因数分解[^2]。 在最坏情况下（即测试对象是一个大合数），此过程涉及遍历所有小于等于\(\sqrt{n}\) 的可能因子。因此，在这种情形下，基本试除法的时间复杂度大约为 \(O(\sqrt{n})\) [^4]。 ```cpp void factorize(int num){ for (int d = 2; d * d <= num; ++d){ while(num % d == 0){ printf("%d ", d); num /= d; } } if(num > 1) printf("%d",num); // 处理剩余的大于 sqrt(n) 的唯一质因子 } ``` #### 利用预计算的最小质因子数组加速质因子分解 为了提高效率并减少重复工作量，可以通过预先构建一个记录各位置上最小质因子信息的数据结构来进行优化。具体来说就是利用欧拉筛找到每个数对应的最小质因子，并将其存储起来供后续查询使用。这样做的好处在于能够显著降低单次求解所需消耗的时间资源，使得整体性能达到接近线性的水平——即平均情况下的时间复杂度约为 \(O(\log n)\)[^3]。 ```cpp const int N = 1e6 + 7; bool is_prime[N]; int min_factor[N]; // 初始化函数用于填充min_factor[] 数组 void init(){ memset(is_prime,true,sizeof(is_prime)); for(long long i=2;i<N;++i){ if(!is_prime[i]) continue; min_factor[i]=i; for(long long j=i*i;j<N;j+=i){ is_prime[j]=false; if(min_factor[j]==0) min_factor[j]=i; } } } // 实际执行质因子分解操作 vector<int> factors(int n){ vector<int> res; while(n!=1 && n>=N){ res.push_back(min_factor[n]); n/=min_factor[n]; } if(n>1&&n<N)res.push_back(n); sort(res.begin(),res.end()); return res; } ``` 综上所述，基于不同场景和技术手段的选择，可以在C语言环境中有效地完成质因子分解任务，并获得较为满意的运行速度表现。