Speeding up my implmentation of project euler 3rd challenge

Question

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.

Did you look at the forum related to the question (on the right of it) on Project Euler (when you solved it)? They are often nice mathematical approaches explained. — Alexis C., Mar 13 '14 at 20:05
@ZouZou no I wanted to come here first, guess I am a little to comfortable coming here. — user2405469, Mar 13 '14 at 20:06
Maybe [CodeReview](http://codereview.stackexchange.com/) is a better place for this kind of question. — Stefan Freitag, Mar 13 '14 at 20:12
Duplicate of http://stackoverflow.com/questions/22153481/advice-on-how-to-make-my-algorithm-faster, http://stackoverflow.com/questions/22092735/project-euler-3-get-largest-prime-factor-of-a-number, http://stackoverflow.com/questions/15279278/finding-largest-prime-number-out-of-600851475143/15292911#15292911 and generally everything under http://stackoverflow.com/search?tab=newest&q=600851475143 — Lutz Lehmann, Mar 14 '14 at 15:44

Elliott Frisch · Accepted Answer · 2014-03-14T18:45:21.463

1

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 */
}

edited Mar 14 '14 at 18:45

answered Mar 13 '14 at 20:08

Elliott Frisch

198,278
20
158
249

1

Then you will need to change the "if" into a "while" to catch prime factors with higher multiplicity. -- Also use `i <= n/i` in the outer loop to avoid checking for numbers that can never be prime factors. -- One could also check for factors 2 outside of the loop and then leave all other even values of i out by starting with 3 and increasing by 2. – Lutz Lehmann Mar 14 '14 at 15:41

score 0 · Answer 2 · answered Mar 13 '14 at 20:21

0

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.

answered Mar 13 '14 at 20:21

This is bad advice, since from floor(sqrt(N)), which is much smaller than N/2 for large N, up to N there is at most one prime factor of N. – Lutz Lehmann Mar 14 '14 at 15:48

Speeding up my implmentation of project euler 3rd challenge

2 Answers2