I've solved Project Euler #3, but solving the same in Hacker Rank which has time constraint of < 4 seconds doesn't work. I've tried using the square root solution for speeding up but it fails.
Example:
The prime factors of 10000001 are 11 and 909091, we have sqrt(10000001) = 3162, if we check all primes from 2 to 3162, we can only have 11, after loop terminated, the result will be 11, incorrect answer.
So, when I use num/2 the running time is significantly increased.
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);
}
}
}