Is this an efficient type of sieve?

Question

Let $f(n)$ be the nth number of the form $6k\pm1$, which can be defined by $f(n) = 3n + \frac{3}{2} - \frac{(-1)^n}{2}$.

Now $f(n)$ obviously outputs all primes $p \gt3$, but also composite numbers whose factors were previously given by $f(n)$. (In other words, a composite number produced by $f(n)$ never has 2 or 3 as a factor.)

A way of avoiding these composites is based on a growing set of simple modulo-rules and the previous outputs of $f(n)$:

Given $f(n) = a$, where $a$ is prime, every following input $n^*$ which satisfies $n^* \equiv n\pmod{2a}$ or $n^* \equiv b_n\pmod{2a}$ will output a composite with $a$ as a factor, where $b_n$ is the nth element of the sequence $\{8,11,18,21,28,31,38,41,48,...\}$

(Please bear with me, I'm afraid this part is a bit confusing to get across, so I'll give with some examples)

• $f(1) = 5$, so every following $n$ which is $\equiv 1\pmod{10}$ or $\equiv 8\pmod{10}$ will produce a composite with 5 as a factor.
• $f(2) = 7$, so every following $n$ which is $\equiv 2\pmod{14}$ or $\equiv 11\pmod{14}$ will produce a composite with 7 as a factor.
• $f(3) = 11$, so every following $n$ which is $\equiv 3\pmod{22}$ or $\equiv 18\pmod{22}$ will produce a composite with 11 as a factor.
• $f(4) = 13$, so every following $n$ which is $\equiv 4\pmod{26}$ or $\equiv 21\pmod{26}$ will produce a composite with 13 as a factor.

My main question is: Is this an efficient type of sieve? Because it knows no upper bounds, outputs every prime $p\gt3$ without skipping any and the next input is given by a set of modulo-rules, which should be fast to compute.

My side question is: Is it possible to derive a fomula for every modulo-rule like $f(n)$ for $6k\pm1$? (With that I mean to create a formula which outputs all numbers which satisfy the rule)

Answer 1

You have an interesting idea. However, regarding your question about it being efficient, if you mean compared to the current state of the art prime generating algorithms, then I believe the answer is unfortunately no. Note I am not an expert myself regarding the various algorithms used for generating primes, but I'm currently doing some prime research so I have investigated what method might work best for me, and have implemented plus optimized a basic solution, so I have some knowledge about this area.

Note your formula to determine composites uses up to $2$ modulus calculations to check whether or not a value is a multiple of each prime. This could be made somewhat more efficient by just getting the integer remainder and then using it to do the $2$ comparisons. However, modulus operations are not particularly efficient apart from using certain constants that a good optimizing compiler will do more efficiently in certain cases (e.g., a bit shift for a power of 2). Instead, according to Optimizing software in C++, in section 14.5 Integer Division, it says "Integer division takes much longer time than addition, subtraction and multiplication (27 - 80 clock cycles for 32 - bit integers, depending on the processor)".

As for reducing the number of values to check, among the odd integers, using just $6k \pm 1$ means you are only bypassing the ones of the form $6k + 3$, so you are checking $\frac{2}{3}$ of them. However, with various Wheel factorization methods, you can get a considerably better reduction in the number of values to check, so at least some of the fastest prime generation algorithms use this.

Another important issue, especially for modern computers, that many people are not aware of is the degree that the amount of memory your program is actively using compared to how much & how fast your memory cache can affect the overall speed. Although processor speeds have improved considerably, at least up until a few years ago, memory speeds have not improved as much since about $10$ or $15$ years ago, so the memory cache has become a more important issue. In fact, due to the nature of what I'm doing, I estimate that it affects around $70$ or $80$ percent of my program speed. With your algorithm, you could store all of the $b_n$ values in memory, which would use more of the memory cache, or just calculate the second value from the first, but this will take some more processor time instead.

For my research, I found & adapted a fairly basic, but relatively efficient, Segmented sieve of Eratosthenes. Although it is fairly good as it is, I made it more efficient by replacing C++ vectors with C type fixed arrays, using bits to store certain values instead of bytes (to help with the memory cache issue), etc. Nonetheless, note that the PrimeSieve library which this originally came from is now much more efficient, but I didn't use it for various reasons of adaptability, complete confidence in understanding it, easy distribution of it, etc., with the segmented sieve being efficient enough (especially after my enhancements) for my purposes.

As for your side question, I have not checked into it to any extent, but I believe it would be possible to derive other modulo type checks.

Good luck with your investigations into methods to generate prime numbers. I hope that you someday find an improvement to the state of art methods.