我正在尝试解决Euler项目中的问题3:
13195的主要因素是5、7、13和29。
600851475143的最大素数是多少?
这是我的代码:
import java.util.ArrayList;
public class Test {
public static void main(String[] args){
long max = 600851475143L;
ArrayList<Long> primes = new ArrayList<>();
primes.add((long) 2);
boolean prime = true;
for (long i = 3; i <= max; i += 2){
for (long j = 3; j < Math.sqrt(i); j++){
if (i % j == 0){
prime = false;
break;
}
}
if (prime) primes.add(i);
else prime = true;
}
for (int i = primes.size() - 1; i >= 0; i--){
if (max % primes.get(i) == 0){
System.out.println(primes.get(i));
return;
}
}
}
}
代码不输出任何东西,它只是给我一个空白屏幕。请不要为我解决问题,只需告诉我是什么错误阻止了它的输出。
您确定您的程序已完成吗?在下面添加了以下代码,看起来第一个for循环将需要很长时间才能完成,这可能就是为什么看不到任何输出的原因。要查看进度,请尝试添加如下打印声明:
import java.util.ArrayList;
public class Test {
public static void main(String[] args){
long max = 600851475143L;
ArrayList<Long> primes = new ArrayList<Long>();
primes.add((long) 2);
boolean prime = true;
for (long i = 3; i <= max; i += 2){
if(i % 1000005 == 0)
System.out.println("i = " + i);
for (long j = 3; j < Math.sqrt(i); j++){
if (i % j == 0){
prime = false;
break;
}
}
if (prime) primes.add(i);
else prime = true;
}
for (int i = primes.size() - 1; i >= 0; i--){
if (max % primes.get(i) == 0){
System.out.println(primes.get(i));
return;
}
}
}
}
您在没有素数时也浪费时间计算所有素数。
max
直到不再可除。假设您正确找到素数(我相信您是这样),请考虑以下因素:
primes = 2,3,5,7,11,13
max = 99
is 99 divisible by 2 - no, try next prime.
is 99 divisible y 3 - yes
max = 33
is 33 divisble by 3 - yes
max = 11
is 11 divisible by 3 - no
by 5 - no
by 7 - no
by 11 - hey, max is a prime! And it must be the largest because
it can't be reduced anymore.