我正在开发一个用 Java 实现的质因数分解程序。 目标是找到 600851475143 ( Project Euler problem 3 ) 的最大质因数。 我想我已经完成了大部分工作,但我遇到了一些错误。 另外,我的逻辑似乎不对,特别是我设置的用于检查数字是否为素数的方法。
public class PrimeFactor {
public static void main(String[] args) {
int count = 0;
for (int i = 0; i < Math.sqrt(600851475143L); i++) {
if (Prime(i) && i % Math.sqrt(600851475143L) == 0) {
count = i;
System.out.println(count);
}
}
}
public static boolean Prime(int n) {
boolean isPrime = false;
// A number is prime iff it is divisible by 1 and itself only
if (n % n == 0 && n % 1 == 0) {
isPrime = true;
}
return isPrime;
}
}
编辑
public class PrimeFactor {
public static void main(String[] args) {
for (int i = 2; i <= 600851475143L; i++) {
if (isPrime(i) == true) {
System.out.println(i);
}
}
}
public static boolean isPrime(int number) {
if (number == 1) return false;
if (number == 2) return true;
if (number % 2 == 0) return false;
for (int i = 3; i <= number; i++) {
if (number % i == 0) return false;
}
return true;
}
}
最佳答案
为什么要把事情搞得这么复杂?您不需要执行isPrime()之类的操作。除以它的最小除数(素数)并从这个素数开始循环。这是我的简单代码:
public class PrimeFactor {
public static int largestPrimeFactor(long number) {
int i;
for (i = 2; i <= number; i++) {
if (number % i == 0) {
number /= i;
i--;
}
}
return i;
}
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(largestPrimeFactor(13195));
System.out.println(largestPrimeFactor(600851475143L));
}
}
关于java - Java 中的质因数分解程序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4273368/