问题3－600851475143的最大质因数

问题描述如下：

“13195的质因数（或者叫素因子，素因素）为5，7，13和29，求600851475143的最大质因数是多少？”

 

这里质因数的概念就不赘述了。

 

给出代码如下：

 

private static Long getTheLargestPrimeFactor(Long n) {
		Long returnFactor = 1L;
		for (Long factor = 2L; n > 1; factor++) {
			if (n % factor == 0) {
				n /= factor;
				returnFactor = factor;
				while (n % factor == 0) {
					n /= factor;
				}
			}
		}
		return returnFactor;
	}

 

  可以得出答案6857。

 

判断的条件是不是可以有所变化呢，我们知道一个数的质因数不能大过一个数的平方根，将设一个数为n，其任何质因数primefactor <= n的平方根。

那就可以将判断条件修改，如下：

 

private static Long getTheLargestPrimeFactor1(Long n) {
		Long returnFactor = 1L;
		Double LargestFactor = Math.sqrt(n);
		for (Long factor = 2L; factor <= LargestFactor; factor++) {
			if (n % factor == 0) {
				n /= factor;
				returnFactor = factor;
				while (n % factor == 0) {
					n /= factor;
				}
			}
		}
		return returnFactor;
	}

 

 

另外，是不是还有一些其他的方面有所改进呢？

我们考虑到2是所有质因数中唯一的偶数，可以在此方面下功夫，不说什么了，贴代码：

 

private static Long getTheLargestPrimeFactor2(Long n) {
		Long returnFactor = 1L;
		Long factor = 2L;
		Double LargestFactor = Math.sqrt(n);
		if (n % factor == 0) {
			n = n / factor;
			returnFactor = factor;
			while (n % factor == 0) {
				n /= factor;
			}
		} else {
			factor = 3L;
		}
		for (; factor <= LargestFactor; factor += 2) {
			if (n % factor == 0) {
				n /= factor;
				returnFactor = factor;
				while (n % factor == 0) {
					n /= factor;
				}
			}
		}
		return returnFactor;
	}

 

 

到此结束，请不吝赐教！

@anthor ClumsyBirdZ

评论

2 楼 zhou_zhihao 2010-11-29  

/**
	 * 最原始的实现
	 * 对于给定的n,使factor=2,3,4,5,6...,对于每个factor,当factor能被n完全整除时,就到下一个factor.
	 * 可以预见,所有被整除的factor都是质因数,当所有小的因数都被整除时,n将会变为1
         * 如n为20,factor为2时,20%2=0,n=n/2,n变为10,returnfactor为10,10%2=0,n=n/2,n变为5,(整除时将某一个因数整除完)然后下一个factor3,4,5,n%5=0,returnfactor=5,n变为1,跳出循环
	 * @param n
	 * @return
	 */
	private static Long getTheLargestPrimeFactor4(Long n) {
		Long returnFactor = 1L;
		for (Long factor = 2L; n > 1; factor++) {
			if (n % factor == 0) {
				n /= factor;
				returnFactor = factor;
				while (n % factor == 0) {
					n /= factor;
				}
			}
		}
		return returnFactor;
	}

1 楼 jy1245626 2010-11-29  

第一个方法能不能加点注释，看不太懂。自己实现的和你的对比起来，代码多太多了，谢谢