[NOIP2012 普及组] 质因数分解

· · 个人记录

第一次摸到这道题还想了有一会儿，又是质因数相乘的积，又是较大，

突然反应过来这是最小质因数，

做完看了一圈题解，发现好像没几个注意到一个很重要的细节

仔细看题，你会发现对于这个正整数n它一定是两个质数相乘，

换而言之，如果你找到了n除1和本身外的任意因数，那么它一定是质数，

也就是说，对于你从2开始找到的第一个质数，n/它就是我们要的答案，并且这个数一定是质数，也就是答案一定正确

这太简单了，那么我们不妨对这个题目进行一个思路拓展，

对于一个正整数n，假设它由多个质数相乘构成

其实仔细想想思路还是很简单，对于任意的n，假设你去分解它，把它变成除1和本身的所有因数相乘的积，

那么对于最小的因数a，它一定是质数，否则它一定会被分成更小的质因数相乘的结果，

也就是说，从2开始去寻找可以整除n的数a，对于可能存在的，它的倍数构成的合数，在一定会在当前这步被分解掉，

也就说，对于这个因数a的倍数合数，一定会在当前这步被预处理解决，

那么这样就可以得到n的最小质因数a，当然这样得到的n/a一定不是质数，

所以我在代码里写的朴素根号n判断其实多此一举，check并不需要

这段补充拓展只是一个思路的提供，原理叫什么我忘记了

那么回到这道题，最小质因数代码成立吗？

当然成立，因为对于任意的n，它应该只有4个因数，1，最小质因数a，n/a,n四个数

显而易见，这样由方案2搜索出来的a和方案1搜索出来的a是完全一致的

因为二者寻找到的第一个a一定是最小质因数，否则它会被分解成两个更小的a

到这里，你会发现方案1和2的本质是一样的，都是从小开始搜索，保证找到的第一个因数一定不会被分解，

差别在于方案1仅针对这道题的情况进行了分析，而方案2则是对方案1思路的总结和拓展上升。

也就是说，去掉题目条件限制，方案2的搜索方式依然可以证明成立，

思路讲完了，代码在下面

AC代码(一)：

#include<iostream>
using namespace std;
int n,rec=-1,n1;
bool check(int a) {
    for(register int i=2; i*i<=n; i++) {
        if(a%i==0) {
            return false;
        }
    }
    return true;
}
int main() {
    scanf("%d",&n);
    n1=n;
    for(register int i=2; i*i<=n; i++) {
        if(n%i==0) {

            printf("%d",n1/i);
            return 0;

        }
    }
    cout<<"Wrong!";
    return 0;
}

AC代码(二):

#include<iostream>
using namespace std;
int n,rec=-1,n1;
bool check(int a) {
    for(register int i=2; i*i<=n; i++) {
        if(a%i==0) {
            return false;
        }
    }
    return true;
}
int main() {
    scanf("%d",&n);
    n1=n;
    for(register int i=2; i*i<=n; i++) {
        if(n%i==0) {
check:
            n/=i;
            if(n%i==0){
                goto check;
            }
            if(check(n1/i)==true) {
                printf("%d",n1/i);
                return 0;
            }
        }
    }
    cout<<"Wrong!";
    return 0;
}