Memory saving for generating larger prime numbers

[neur0maniak]

For primes > 210, there are only 48 answers to: x MOD 210, that a prime can exist at.
I believe it is also true for any prime > 7

1,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,121,127,131,137,139,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209

If 2,3,5,7 were automatically assumed to be prime, and then a mapping using the above was made for the bitarray, you would only need to use 22.86% of the memory. Allowing you to create primes 437.5% bigger, without going into virtual memory.

A simpler version of this would be: x MOD 6 in [1,5] for any prime > 3, but this would give 66.66% memory saving, compared to 78.14% using MOD 210.

[rbergen]

@neur0maniak I'm moving this to Discussions.

[rbergen]

The approach of using known primes under a certain threshold is the foundation for algorithms that are labeled as "wheel" algorithms in the context of this project. The main reason for their use is not saving memory though, but increasing prime discovery speed. There is at least one implementation that takes this to the point where it uses the 5760 known primes under 30030 as a basis.

[neur0maniak]

Apologies for not putting it into discussions. I didn't notice it, I am not a big user of github.
Thank for giving me the name of this idea. It was just a pattern I had noticed when playing with/creating prime number generators, I didn't know there were actual algorithms based on it.

[rbergen]

Apologies for not putting it into discussions. I didn't notice it, I am not a big user of github.

Don't worry about it. GitHub's UI doesn't draw much attention to the feature, for some reason (I'd put it before Issues in the link bar, but who am I?)

Thank for giving me the name of this idea. It was just a pattern I had noticed when playing with/creating prime number generators, I didn't know there were actual algorithms based on it.

It gets better, it even has a Wikipedia page: https://en.wikipedia.org/wiki/Wheel_factorization