CODEWITHSUNDEEP
java
user2405469
user2405469

Reputation: 2003

Speeding up my implmentation of project euler 3rd challenge

I have gone from 96 lines to 17 lines taking hits at this one, this is what I am left with after all of that effort:

public class IntegerFactoriseFive {

    public static void main(String[] args)
    {
        long n = 600851475143L;
        for (long i = 2; i <= n; i++)
        {
            if (n % i==0)
            {
                System.out.println(i);
                n = n / i;
                i = 2;
            }
        }
    }

}

Is there any way to make it faster? I'm not suggesting that it isn't quick enough already, but for the sake of it and for improving the way I tackle problems in the future. My other solutions were taking forever, I was using recursion, I even only iterated up to the square root of the numbers I was checking (from early school maths I know to only check up to the square root, it is a lot quicker), but it was still to slow, in the end iterating by one and dividing this huge number was the wrong way to go about it, so instead I figured that dividing the number as much as possible was the only way I could do it in any good time. Suggestions please, as you can see by the class name it is my fifth official solution for it that is the quickest of the ones I came up with.

Upvotes: 0

Views: 70

Answers (2)

Elliott Frisch
Elliott Frisch

Reputation: 201467

Remove i = 2; in your if clause (and make it a while loop). Restarting your loop will not find any more cases. That is,

while (n % i == 0)
{
  System.out.println(i);
  n = n / i;
  // i = 2; /* Ouch */
}

Upvotes: 1

user3396542
user3396542

Reputation:

you can make it fast by using Multithreading, e.g u can use two threads, one starts from the beginning until the half, and the other starts from the end until the half. Thus,you made it fast x2 and The speed depending on the number of Threads.

Upvotes: 0

Related Questions