find largest prime factor using java

845 views Asked by At

I want to find the largest prime factor of 600851475143.I wrote the following code but I am not getting the correct answer. Please help me ...

public class A {
  public static void main(String[] args) {

    int arr[]=new int[25];
    int large=0;
    long n=600851475143L;
    long x=(long) Math.sqrt(n);
    Top:  for(int i=3;i<x;i=i+2)
    {
      if(n%i==0)
      {
        n=(long) n/i;
        for(int j=0;j<25;j++)
        {
          arr[j]=i;
        }
        break Top;
      }
    }
    //System.out.println(arr);
    int num=arr.length; 
    for(int i=0;i<num-1;i++)
    {
      if(arr[i]>arr[i+1])
      {
        large=arr[i];
      }
      else
      {
        large=arr[i+1]; 
      }
    }

    System.out.println(large); 
  }
}
1

There are 1 answers

1
jknam On
public class LPF {
    public static void main(String[] args) {
        int lpf= 2;
        long num = 600851475143L; 
        while (num > lpf) {
            if (num % lpf == 0) {
                num/=lpf;
                lpf = 2;
            } else {
                lpf++;
            }
        }
        System.out.println("Largest prime factor is " + Integer.toString(lpf));
    }
}

This is a simple implementation to find the largest prime factor of this number. A way to optimize this is to not increment lpf by 1 and instead set it to the next highest prime number.