最大质因数_牛客博客

题目描述如下

最大质因数
13195的所有质因数为5、7、13和29。

600851475143最大的质因数是多少？

这个题怎么做呢　？？

难道我先要求出　根号６００８５１４７５１４３　以内的所有素数，然后从大到小的比较吗？

当然也是可行的，不过我们换一种看待数字的方式。

比如　看成一系列素数相乘的形式:

a = p₁^a1 ×p₂^a2×p₃^a3×p₄^a4 …

啥意思呢　比如　１２　可以表示为　2 ² ×　３¹

那么当表示成这个形式，我们要找的最大的质因数就呼之欲出了

不过好像还差一点

那怎么找到最大的？

先看另一个问题

如果给你一个数字，让你找到最小的素因子，你能找到吗？

简单呀，从２开始找，每次加一，直到可以整除，就是最小的

int x，ｉ　＝　２; // x 为该数字，ｉ所求为ｘ的最小素因子
while(x % i != 0){
   
    i ++;
}
printf("%d\n",i);//此时就找到了ｘ的最小素因子

ＯＫ不

那找最大的呢？

转化一下问题

每次都把目前找到的素因子从ｘ中除掉，最后找到的就是最大的。。

不断把问题转化为寻找目前最小的素因子

/************************************************************************* > File Name: 2.c > Author:Gin.TaMa > Mail:1137554811@qq.com > Created Time: 2019年01月02日 星期三 21时55分11秒 ************************************************************************/

#include<stdio.h>
#include<inttypes.h>
int main(){
   
    int64_t num = 600851475143,x = 2,ans = 0;
    while(num != 1){
   
        while(num % x != 0){
   
            x ++;
        }
        ans = x;
        // 除掉ｎｕｍ中的所有值为ｘ的素因子
        while(num % x == 0){
   
            num /= x;
        }
        x ++;
    }
    printf("%"PRId64"\n",ans);
}

ＯＫ　自此最大质因数的问题就解决了