最大质因数 最大回文数乘积

Java每日练习题及题解——11月16日

13195的质因数分别为5，7，13与29，600851475143最大的质因数是多少？

6857

首先在拿到这个题目，首先我们需要知道什么是质因数？它有哪些性质？
质因数：质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。 除了1以外，两个没有其他共同质因子的正整数称为互质。 因为1没有质因子，1与任何正整数（包括1本身）都是互质。 正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。
质因数的性质：

1. 正整数的因数分解可将正整数表示为一连串的质因子（质数）相乘。
2. 素数x素数=合数，素数x合数=合数，合数x合数=合数。
3. 如果一个合数n有超过√n的质因数，那么有且只有一个，且为自身。

首先写一个判断是否为质数的函数，然后进行循环，只要满足i可以被n整除且i为质数，那么就break，得到最大的质因数。

//方法一:
//判断一个数是否是质数
    public static int isPrime(long x){
        for(int i=2;i*i=2;i--)//最小的质数就是2，所以除以2
        {
            if((n%i==0)&&(isPrime(i)==1))
            {
                return i;//i既是原数的最大因数，同时也是质数
            }

        }
        return 0;
    }

}

PS:此方法耗时过长，会导致直接超时！！！不建议使用！！！

由性质1，2可知任意一个整数都可表示为多个质数的乘积（即x=x1x2…*xn）。所以从i质数2开始，我们用n去除以i，如果n能够被i整除，则定义一个变量res记录i，再用n除以i;否则进行i++。如此进行下去，逐步对n进行瓜分，最终当n=1时结束循环的时候，较小的质因数已经早被瓜分掉了，最后剩下的i一定是最大的质因数，当n/i==1；即此时n=i,此时的i即为最大的质因数。
故采取这种逐渐逼近的方法的效率要比第一种方法效率高。

//    方法二：getMax2
    public static long getMax2(long n){
        long i=2;
        long res=1;
        while(n>2){
            if(n%i==0){
                n/=i;
                res=i;
            }else{
                i++;
            }
        }
        return res;
    }

从方法二我们可以看出，其实最终最大的质数其实是一直藏在x=x1x2…*xn式子右边的，直到i等于这个数。
但是由性质三可知：“如果一个合数n有超过√n的质因数，那么有且只有一个，且为自身。”，
所以任意一个整数的最大质因数有两种情况：1.为它本身；2.小于√n。
所以方法三在方法二的基础上更改了循环终止的条件，去掉了不必要的步骤，以此来提高效率。

//    方法三：
public static long getMax3(long n){
        long res=0;
        for(int i=2;i*i<=n;i++)
        {
            while(n%i==0){
                res=i;
                n/=i;
            }
            if(n==1)
                break;
        }
          if(n!=1)    //如果n不等于1，说明存在一个大于根号n的质因数，此时最大质因数等于当前的n
            res = n;
          return res;
}

回文数即从正反两边读都是一样的数，两个二位数的乘积中最大的回文数为9009=91*99，寻找两个三位数乘积中最大的回文数。

906609