# Got stuck at Project Euler’s question 3 i.e. finding the largest prime factor of a given number. Please see details

###### Posted By: Anonymous

So I designed this code (given below) for the question & it seems to be giving all the answers there are but for some reason I’m not able to pass my test cases in the Hackerrank Question except for the sample one.

My Code :

```
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for(int a0 = 0; a0 < t; a0++){
BigInteger n = new BigInteger(in.next());
BigInteger max = BigInteger.valueOf(1);
for(BigInteger i=BigInteger.valueOf(2);i.multiply(i).compareTo(n)<=0;i=i.add(BigInteger.ONE))
{
if(i.isProbablePrime(1) && n.mod(i).compareTo(BigInteger.valueOf(0))==0 && i.compareTo(max)>=0)
{
max = i;
n = n.divide(i);
}
}
if(n.isProbablePrime(1))
max = n;
else if(n.divide(BigInteger.valueOf(2)).isProbablePrime(1))
max = n.divide(BigInteger.valueOf(2));
System.out.println(max);
}
}
}
```

I’m getting the same output for each input as this website here.

Can anyone please look have a look at my code & point out where am I going wrong. I’m not looking for new code or logic, I just want to know how & why my code or logic is wrong. Can anyone help?

Thanks in advance.

**EDIT : NEW CODE** **Found The Solution** Thanks to @Douglas for helping me with hints

```
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for(int a0 = 0; a0 < t; a0++){
long n = in.nextLong();
long max = 1;
while(n%2==0)
n = n/2;
if(n==1)
max = 2;
for(long i=3;i*i<=n;i+=2)
{
while(n%i==0 && i>=max)
{
max = i;
n = n/i;
}
}
if(n>2)
max = n;
System.out.println(max);
}
}
}
```

The code above runs perfectly fine & passes all the testcases.

## Solution

You have three problems with this code:

- An actual bug. You don’t handle when a prime divides the number multiple times. I’m fairly sure the four lines before the
`println`

output are a workaround you put in when you encountered a failure this causes, that fixed the specific failure you found but don’t actually address the root cause. I just tested it, your code outputs 3 for the input 252. The correct output for 252 is 7. - Part of your code invokes a library method that may be significantly expensive. You should not be using
`isProbablePrime`

. - Your algorithm’s logic scales poorly. Hackerrank’s test cases probably include something where the correct output is something like 20 digits long. A major point of Project Euler is that it’s not enough to write code that will find the correct answer. You need to write code that will find the correct answer
**efficiently**. To fix this, you will need new logic for the fundamental design of the program.

###### Answered By: Anonymous

Disclaimer: This content is shared under creative common license cc-by-sa 3.0. It is generated from StackExchange Website Network.