我已经解决了项目Euler＃3，但是在时间限制小于4秒的Hacker Rank中解决了同样的问题。我尝试使用平方根解决方案来加快速度，但是失败了。
例：
10000001的素数是11和909091，我们有sqrt（10000001）= 3162，如果检查从2到3162的所有素数，则只能有11，在循环终止后，结果将是11，错误答案。
因此，当我使用num / 2时，运行时间将大大增加。
public class Solution {
static boolean checkPrime(long num){
boolean toret = true;
long sq = (long) Math.sqrt(num);
for(long i=2; i<=sq; i++){
if(num%i ==0)
toret = false;
}
return toret;
}
static long gimmeAns(long num){
ArrayList<Long> al = new ArrayList<Long>();
int q = 0;
long[] list = new long[10];
long sq = (long)Math.sqrt(num);
long sqint;
boolean flag = true;
if(num < 0){
for(long i =3; i<=num; i+=2){
if(num%i == 0)
al.add(i);
}
}else{
//for(long i =3; i<=sq; i+=2){
//if(num%i == 0)
//al.add(i);
//}
boolean isPrimeCheck = checkPrime(num);
if(isPrimeCheck){
al.add(num);
}
for(long i =3 ; i<= num/2 ; i+=2){
if(num%i==0){
al.add(i);
}
}
}
Iterator it = al.iterator();
while(it.hasNext()){
long curr = (long) it.next();
flag = true;
long squrt = (long) Math.sqrt(curr);
for(long i=2; i<=squrt; i++){
if(curr%i == 0)
flag = false;
}
if(flag == true){
list[q++] = curr;
}
}
return list[q-1];
}
public static void main(String[] args) {
long numberCases;
Scanner in = new Scanner(System.in);
numberCases = in.nextLong();
long result = 0;
for(long i=0; i< numberCases; i++){
long num = in.nextLong();
result = gimmeAns(num);
System.out.println(result);
}
}
}
最佳答案
遍历所有sqrt（n）的数字呢？每次找到素数，都用该数除以素数（并且不增加该数）。
现在，当您达到sqrt（n）时，将比较找到的最新分频器与剩余数字。您必须返回两者中的最大值：
long n = sc.nextLong();
int k = 0x02;
int l = (int) (Math.sqrt(n)+1);
while(k < n && k <= l) {
if(n%k == 0) {
n /= k;
} else {
k++;
}
}
return Math.max(n,k);
在这种情况下，如果一个数字有两个质数，则较小的一个将在while循环中捕获，从而导致
n现在将具有较大的值。