Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- KX Community
- :
- Discussion Forums
- :
- kdb+ and q
- :
- Re: Q For Problems - Episode 3

Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Q For Problems - Episode 3

Options

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2022.10.20 07:40 AM

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:

Blog post: Finding primes with q

Thanks

1 REPLY 1

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2022.10.20 04:12 PM - edited 2022.10.20 04:13 PM

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.

Main Office Contacts

**EMEA**

Tel: +44 (0)28 3025 2242

**AMERICAS**

Tel: +1 (212) 447 6700

**APAC**

Tel: +61 (0)2 9236 5700

Useful Information

Resources

Popular Links

Follow Us

KX. All Rights Reserved.

KX and kdb+ are registered trademarks of KX Systems, Inc., a subsidiary of FD Technologies plc.