Memory saving for generating larger prime numbers #330
Replies: 1 comment 3 replies
-
|
@neur0maniak I'm moving this to Discussions. |
Beta Was this translation helpful? Give feedback.
-
|
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. |
Beta Was this translation helpful? Give feedback.
-
|
Apologies for not putting it into discussions. I didn't notice it, I am not a big user of github. |
Beta Was this translation helpful? Give feedback.
-
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?)
It gets better, it even has a Wikipedia page: https://en.wikipedia.org/wiki/Wheel_factorization |
Beta Was this translation helpful? Give feedback.
-
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.
Beta Was this translation helpful? Give feedback.
All reactions