我为欧拉项目的第二个问题编写了以下程序,针对这个问题:“欧拉项目3:最大素因子”,它应该打印出所提供输入的所有最高素因子。
import java.util.Scanner;
public class euler_2 {
public static boolean isPrime(int n) {
if (n % 2 == 0) return false;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0)
return false;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
for (int i = 0; i < a; i++) {
int b = sc.nextInt();
for (int j = b; j >= 1; j--) {
boolean aa = isPrime(j);
if (aa == true && b % j == 0) {
b = j;
break;
}
}
System.out.println(b);
}
}
}
为了使程序执行得更快,我可以对程序进行哪些更改有什么更好的算法来解决这个问题?
最佳答案
你的方法的问题是,对于每一个数N
,你尝试每一个小于或等于N
的数,不管它是素数,之后是N
的除数。
明显的改进是首先检查它是否是除数,然后才检查它是否是素数。但很可能这并没有多大帮助。
你能做的只是开始检查每个数字是否是一个数的除数如果是除数,就把它除掉你继续这个直到sqrt(N)
。
我很久没有用java做过任何事情了,但这里是Go实现,很可能任何java人都可以将其转换为java。
func biggestPrime(n uint64) uint64 {
p, i := uint64(1), uint64(0)
for i = 2; i < uint64(math.Sqrt(float64(n))) + uint64(1); i++ {
for n % i == 0 {
n /= i
p = i
}
}
if n > 1 {
p = n
}
return p
}
使用我的算法需要O(sqrt(N))才能找到一个数的最大素数你的情况是
O(N * sqrt(N))