Q For Problems - Episode 3

[jkane17]

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.

Links:

qForProblems Git Repo  

Blog post: Finding primes with q 

Thanks

[cillianreilly]

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.