九乡新闻网铁血联盟2野火6.0:欧拉项目第三题 Problem3
来源：百度文库 编辑：九乡新闻网 时间：2024/04/28 18:27:38
欧拉项目第三题 Problem3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
单词：
prime factors:素数
public class Problem3 {
/**The prime factors of 13195 are 5, 7, 13 and 29.
* What is the largest prime factor of the number 600851475143 ?
* 求一个数的最大公因数
* 可以用判定素数的方法
* 也可以用以下方法
*
* @param args
*/
public static void main(String[] args) {
long n =
System.out.println(prime(n));
}
public static long prime(long x){
//求一个数的最大公因数
long n = 2;
while(x > 1){
if(0 == x % n){
x = x / n;
}else{
//System.out.print(n + ", ");
n++;
}
}
return n;
}
}
判定素数法：
public class Problem3 {
/**The prime factors of 13195 are 5, 7, 13 and 29.
* What is the largest prime factor of the number 600851475143 ?
* 求一个数的最大公因数
* @param args
*/
public static void main(String[] args) {
long n =
int k = (int)Math.sqrt(n); //一个数的最大公因数不会超过它的开平方数
if(0 == k % 2){
k++; //如果k为一个偶数，则k=k+1
}
System.out.println(k);
for(int i = k; i > 0; i -= 2){
if(0 == n % i){
//System.out.print(i + ",w ");
if(prime(i)){
System.out.print(i + ", ");
//break;
}
}
}
}
public static boolean prime(long x){
//判定一个数是否为素数
for(long i = 3; i < Math.sqrt(x); i += 2){
if(0 == x % i){
return false;
}
}
return true;
}
}
该数的公因数分别为：6857, 1471, 839, 71, 1；那么最大公因数当然为6857。