Re: How to compress this ?
Posted: Fri Jul 25, 2025 2:27 am
Hello my friends ! I added my remark without making an actual prime number research project... Just a sub-task to make an text editor !
However, here are several answers :
1)
It is a specific challenge, where 1 is considered as prime, and where javascript is used obviously, so unable to work to 64 bits. I am not interested specifically, excepted if it is the zeta of Riemann, sure, but please get the million dollars before publishing it !!!piero wrote:…but if you need the gaps between primes:
https://codegolf.stackexchange.com/ques ... -distances
Here (in this forum) you have a very fast (and furious) algos from fweil, searching very quickly prime numbers to 8 billions of billions (signed 64 bits), with or without task share through TCPIP, because only one computer is not able to do it actually.
viewtopic.php?p=495318
Note that keya asked about the fweil algo : my humble help is here : prime numbers pagination.
2)
@piero and smaag
piero talked about 6N+f(2, x)
and smaag talked about 30N+f(3, x)
(where f(k, x) is a specific serie papipp published on the french forum in 2014)
I am agree with you, but there is a general rule :
pFact(k) * N + f(k, x)
2N+f(1,x) stays the best way (50% optimization of memory or speed)
With 2N (less than 6N, 30N, 210N, etc...) the hardware is very adapted to predictive loops, that is also for that I said it stays the best way.
The gain is less and less important (it is one of the characteristics of prime numbers) :
Code: Select all
mod gain
2N 50%
6N 50% * 33% = 17%
30N 50% * 33% * 20% = 3%
etc...1: 2 mask elements
2: 6 mask elements
3: 30 mask elements
4: 210 mask elements
5: 2K mask elements
6: 30K (#13)
7: 500K (#17)
8: 10M (#19)
9: 223M (#23)
10: 6.5G (#29)
11: 200G (#31)
12: 7 Tera (#37)
13: 304 Tera
@piero what it is not understood is, if we have one of the best algos in the world on this forum, this algo requiring a very complex (and very well worked) source code, if I talk about memory compressing, what I need is a simple code which does not require lots of memory
2N -> 0 mask
6N -> 2 masks
30N -> 12 masks
210N -> 84 masks
2310N -> 924 masks
30030 -> etc...
More we want to be (theorically) fast, far more we need memory...
---> 2N stays the quickest because no mask, no masks list, just CPU internal ops (the fastest), no RAM access
and SIMD optimization is available
It is the 1st argument, not to use this template : the hardware and the temporary memory use.
But there is an other argument, we will see below.
@smaag
32 bits is unsigned, so for 2 times more (+100%) prime numbers, you need only 50% more memory... For unsigned 32 bits, we can used a quad.
Note that Miller Rabin algo is not perfect.
But this means it is not a good way : just it misses anything to be perfect.
Here you have an example of perfect algo, found by a woman. Slower but perfect.
The 2nd argument I wanted to talk about is the loss of density of the prime numbers when we search more and more. On 63 bits signed, it is important, and a loss which does not exist on the first prime numbers, start to be very difficult for number above one billion. Over 10^9, a modulo 30 algo is low.
"My" algo follows the arithmetic. It needs only one bit for prime number between 7 and 89
a: prime number column
b: gap number column
c: gap/2 column : first attachment to 1-or-2 "cursor"
d: resulting list
Code: Select all
a b c dCode: Select all
2 +1 excluded
3 +2 excluded
5 +2 +1 0
7 +4 +2 0
11 +2 +1 0
13 +4 +2 0
17 +2 +1 0
19 +4 +2 0
23 +6 +1 1 +2 0
29 +2 +1 0
31 +6 +2 1 +1 0
37 +4 +2 0
41 +2 +1 0
43 +4 +2 0
47 +6 +1 1 +2 0
53 +6 +1 1 +2 0
59 +2 +1 0
61 +6 +2 1 +1 0
67 +4 +2 0
71 +2 +1 0
73 +6 +2 1 +1 0
79 +4 +2 0
83 +6 +1 1 +2 0
89 +8 +1 2 +2 1 +1 0
97In the same time, with modulo 30, you need 24 bits (3*4-2-2)*3 between 1 and 90.
Then you have a gold age which starts, but it finishes near 100 millions I think... Anyway, it stops anywhere in a limit less than 32 bits in a 64 bits area...
@Lord
You can see a hardwared bitwise sieve of Eratosthene here !