题解：P1075 [NOIP2012 普及组] 质因数分解

ryf2011 · 2025-01-12 09:24:22 · 题解

题目思路

由于 n 的范围很大，我们不能通过直接枚举找到答案，如何解决呢？

我们从小到大寻找第一个 n 的因数，即 n 的最小因数，此时输出 n 除以这个数即为另一个较大的质数。

代码

注：本代码仅供参考。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        if(n%i==0){ //如果 n%i==0，说明找到了 n 的因数，直接输出 n/i，退出循环。 
            printf("%d",n/i); 
            return 0;
        }
    }
    return 0;
} 

后记

更多内容，请移步至 \color{red}\texttt{ryf2011}。