-3

I am getting output for 13195L, 24L, and 23L. But I am not getting output for 600851475143L. The system is going into infinite loop. Please help me identify what is wrong with my code. 

package problem3;

public class problem3_version1 {
    public static void main(String[] args) {
        long dividend = 600851475143L;
        // long dividend=13195L;
        // long dividend=24L;
        // long dividend=23L;
        int num_of_divisors = 0;
        for (long i = dividend - 1; i >= 2; i--) {
            System.out.println("i =" + i);
            int count = 2;
            for (long j = 2; j < i; j++) {
                if (i % j == 0)
                    count++;
                if (count == 3)
                    break;
            }
            if (count == 2) {
                if (dividend % i == 0) {
                    num_of_divisors++;
                    System.out.println("Highest factor is " + i);
                    break;
                }
            }
        }
        if (num_of_divisors == 0)
            System.out.println("The number is prime");
    }
}
Mark Stewart
  • 2,046
  • 4
  • 22
  • 32
nikki123
  • 3
  • 2
  • I would look at your `for (long j = 2; j < i; j++) {` loop; you are incrementing `j` but seeing if it less than `i`. – Mark Stewart Aug 03 '18 at 23:16
  • Or just, *please*, do some **research**, e.g. a web search for [`Find largest prime factor`](https://www.google.com/search?q=Find+largest+prime+factor), which will give you a ton of articles on the topic. – Andreas Aug 03 '18 at 23:20
  • I am finding if "i" is prime or not. So not considering 1 and i itself in the loop. And if its not prime checking if its a factor of the dividend. – nikki123 Aug 03 '18 at 23:38
  • 1
    Your program is not buggy. Strictly speaking, it does not contain an infinite loop. The problem is that it is exceedingly inefficient. It will do something approaching `600851475143L * 600851475143L` divisions ... if the number has no factors. That is a very, very large number of operations. Solution: do some research on *efficient* ways to test for primality. – Stephen C Aug 04 '18 at 03:32
  • Yes, got it. Thank you for the input. – nikki123 Aug 04 '18 at 04:32

1 Answers1

0

try this solution : 

public class LargestPrimeFactor 
{

    public static int largestPrimeFactor(long number) {
        int i;

        for (i = 2; i <= number; i++) {
            if (number % i == 0) {
                number /= i;
                i--;
            }
        }

        return i;
    }

    public static void main(String[] args) {
        System.out.println(LargestPrimeFactor.largestPrimeFactor(600851475143l));
    }

}

The problem was because you have nested loop with very big number, and that what made the loop

Mark Stewart
  • 2,046
  • 4
  • 22
  • 32
Mahmood Zeidat
  • 16
  • 2