View Single Post
Old 2020-04-24, 03:54   #5
Citrix's Avatar
Jun 2003

32×52×7 Posts

Originally Posted by rogue View Post

The Legendre table is easy to generate, but for larger k (> 1e9) it can take more time and a lot of memory to build the table.
For large k values unless the k is very smooth it might be faster to use less memory and use the power residue code (2) instead of a Legendre table.

Legendre tables at best would reduce the number of primes being tested by 50% and are mainly suited for small k and base values.

For large number of k being sieved together Legendre tables are not worth it. They increase the overhead significantly as you previously mentioned.
Citrix is offline   Reply With Quote