cancel
Showing results for
Did you mean:

## Q For Problems - Episode 3

Contributor

Hi everyone,

Please check out episode 3 of the Q For Problems video series.

This covers problem 3 from the Project Euler problem set. Project Euler - Problem 3

This problem wants us to find the largest prime factor of a large number.

It has been split into two parts due to the length of the video.

Part 1 covers the Trial Division algorithm and part 2 covers Pollard's Rho algorithm  for prime factorisation

Feel free to share your own solutions and ideas in the comments.

Thanks

1 Comment
New Contributor III

Similar to your  part 1, but it's not necessary to carry the divisors through each iteration. Divide them out of the target number and repeat the calculation. Lends itself well to using the while overload of /, and is pretty efficient also. This works for odd numbers.

``````q)last -1_(not 1=){7h\$x%mod[x;](2+)/3}\600851475143
6857``````

It might be possible to optimise this a little further by:

1. Precomputing the list of primes less than the square root of the target number and only checking those as divisors.

2. Keeping track of the last number tested so that the calculation doesn't have to start from 3 each time.

But the overhead of implementing these may turn out not to be worth it, and would definitely lengthen the code a lot.

Contributors