【算法】质因子

设置factor结构体

由于2*3*5*7*11*13*17*19*23*29超过int范围，因此数组大小开到10即可：

struct factor{
    int x,cnt;//x为质因子，cnt为其个数
}fac[10];
int num;

关键来了：如果一个数存在1和本身之外的因子，那么一定是在sqrt(n)的左右成对出现的。因此得出一个强化的结论：

对一个正整数n，如果存在有[2，n]之间的质因子：

1、要么这些质因子全部小于等于sqrt(n)

2、要么只存在一个大于sqrt(n)的质因子，而其余质因子全部小于等于sqrt(n)

vector<int>prime;
int num;
int isPrime(int x)
{
    if(x <= 1) return 0;
    for(int i = 2;i <= sqrt(x); i++)
        if(x % i == 0)
            return 0;
    return 1;
}
void findPrime()
{
    for(int i = 1;i < 101;i++)
        if(isPrime(i))
            prime.push_back(i);
}
int main()
{
    findPrime();
    cin>>n;
    for(int i = 0;prime[i] <= sqrt(n) && i<prime.size(); i++)
    {
        if(n % prime[i] == 0)//注意不是n % i 此处是质因子，不是因子
        {
            fac[num].x = prime[i];
            fac[cnt] = 0;
            while(n % prime[i] == 0)
            {
                fac[num].cnt++;
                n /= prime[i];
            }
            num ++;
        }
    }
    if(n != 1)
    {
        fac[num].x = n;
        fac[num++].cnt = 1;
    }
    return 0;
}