Problem 3

问题描述：
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?


找出一个数字的最大因子。

public static boolean IsPrime(long number) {
		int begin = 2;
		int end = (int) Math.sqrt(number) + 1;
		for (int i = begin; i < end; i++) {
			if (number % i == 0)
				return false;
		}
		return true;
	}

	public long FindLargestPrime1(long number) {

		long largest_prime = 1;
		int middle = (int) Math.sqrt(number);
		System.out.println(middle);
		for (int i = middle; i > 1; i--) {
			if (IsPrime(i) && number % i == 0) {
				if (i > largest_prime) {
					largest_prime = i;
				}
				do {
					number = number / i;
				} while (number % i == 0);
			}
		}
		if(IsPrime(number)&&number!=1){
			largest_prime = number;
		}
		return largest_prime;
	}

这个还是有点复杂！

可以改进！
完全可以从2,3...除起来
每次记录下当前的除数就好了~

评论

1 楼 to_zoe_yang 2011-06-12  

public static boolean IsPrime(long number) {
int begin = 2;
int end = (int) Math.sqrt(number) + 1;
for (int i = begin; i < end; i++) {
if (number % i == 0)
return false;
for_count1++;
}
return true;
}

public long FindLargestPrime1(long number) {

long largest_prime = 1;
int middle = (int) Math.sqrt(number);
System.out.println(middle);
for (int i = middle; i > 1; i--) {
for_count1++;
if (IsPrime(i) && number % i == 0) {
if (i > largest_prime) {
largest_prime = i;
}
do {
number = number / i;
for_count1++;
} while (number % i == 0);
}
}
if(IsPrime(number)&&number!=1){
largest_prime = number;
}
return largest_prime;
}

public long FindLargestPrime2(long number){
long largest_prime = 1;
int begin = 2;
long end = number/2;
for(int i=begin; i<end && number!=1;i++){
if(number%i==0){
largest_prime = i;
do{
number = number/i;
for_count2++;
}while(number%i==0);
}
for_count2++;
}
return largest_prime;
}

差距真大
6857 for_count1:47474974
6857 for_count2:6860