苏州网站建设科技有限公司/网站外链平台

题目

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

解析

设n=600851475143(注意数据范围，此处要用long)
第一处：质因数，则要掌握求质因数的方法
第二处：最大即可用一个变量max来比较存储（注意初始化）
注释：质因数既是质子，又是因子，质数即素数（素数除了能表示为自己和1的乘积以外们不能表示为任何其他两个正整数的乘积）；因数的范围为[1,n] ；1不是素数，则从2开始遍历到变量n的二分之一次方，其次需掌握判断是否为素数的方法
注释：
遍历到n的二分之一的原因，假设n的一个较小因子为d，则n%d=0，n/d为整数，n%（n/d)=0;
则d<=n/d则d<=(long)Math.sqrt(n),求出最小的因子，与之对应就可求出最大因子

质数（素数）的判断

//判断是否为质数public  static boolean isPrime(long temp){
//        判断temp是否为质子数long max=(long)Math.sqrt(temp);long i;
//        通过i来遍历for(i=2L;i<=max;i++){if(temp%i==0){
//                表明不是质数return false;}}return  true;}

代码

package edu.wust.competiton;import java.math.BigInteger;public class chapter3 {
//判断是否为质数public  static boolean isPrime(long temp){
//        判断temp是否为质子数long max=(long)Math.sqrt(temp);long i;
//        通过i来遍历for(i=2L;i<=max;i++){if(temp%i==0){
//                表明不是质数return false;}}return  true;}
//    主程序public  static  void main(String[] args){long n=600851475143L;//记录数据long d,max=0;
//        min来记录最大质因子long temp=(long)Math.sqrt(n);for(d=2L;d<=temp;d++){if(n%d==0){if(isPrime(n/d)&&max<n/d){
//                    判断较小因子d与之对应的较大的因子是否为质数同时与max比大小max=n/d;}else if(isPrime(d)&&d>max){
//                    判断较小因子d是否为质数同时与max比大小max=d;}}}if(max!=0){
//            此处的判断是防止某些没有质因数，比如3System.out.println(max);
//        输出最大质因数：6857}}
}

注意

1.较大和较小因子均要判断是否为质数，因为无法确定较大因子是否为质数
2.最后判断一下max，因为我们无法确定是否有质因数