Matrix sieve algorithm for finding prime numbers

Question

I have derived the following theorem:

An odd positive integer $N=6n−1$ is a prime iff neither of two diophantine equations

$6x^2+(6x−1)y=n$

$6x^2+(6x+1)y=n$

has solution.

An odd positive integer $N=6n+1$ is a prime iff neither of two diophantine equations

$6x^2−2x+(6x−1)y=n$

$6x^2+2x+(6x+1)y=n$

has solution.

$x=1,2,3,\ldots;y=0,1,2,\ldots;n=1,2,3,\ldots$

Theorem allows to substitute the task: "Find all primes in the range $(N_1;N_2)$" by the task: "Find positive integers which do not appear in the range $(n_1;n_2)$ in two pairs of $2$-dimensional arrays

$P_1(i,j)=6i^2+(6i-1)(j-1)$

$P_2(i,j)=6i^2+(6i+1)(j-1)$

$i,j = 1,2,3,\ldots$

for primes in the sequence $N=6n-1$.

$P_3(i,j)=6i^2-2i+(6i-1)(j-1)$

$P_4(i,j)=6i^2+2i+(6i+1)(j-1)$

$i,j = 1,2,3,\ldots$

for primes in the sequence $N=6n+1$. Since all primes (except $2$ and $3$) are in one of two forms $6n−1$ or $6n+1$, so we can find primes simply by picking up positive integers which do not appear in these arrays and we need not to perform operations of dividing. See http://www.planet-source-code.com/vb/scripts/BrowseCategoryOrSearchResults.asp?lngWId=3&blnAuthorSearch=TRUE&lngAuthorId=21687209&strAuthorName=Boris%20Sklyar&txtMaxNumberOfEntriesPerPage=25

Can proposed algorithm be regarded as an alternative to sieve of Eratosthenes?

Answer 1

You can simplify by using just one matrix $$P(i,j)=6ij+i-j$$ with $i\geq 2$ and $j\geq 1$

We can find primes (except $2$ , $3$ and $5$) simply by picking numbers $k>1$ which do not appear in this array (except $21$) with:

$p= \frac{(6k-1)}{5}$ if $k\equiv 1 \bmod 5$

and

$p=6k-1$ otherwise

However a faster method is obtained using this code in python:

n=10000000
primes5m6 = [True] * (n//6+1)
primes1m6 = [True] * (n//6+1)
for i in range(1,int((n**0.5+1)/6)+1):
    if primes5m6[i]:
        primes5m6[6*i*i::6*i-1]=[False]*((n//6-6*i*i)//(6*i-1)+1)
        primes1m6[6*i*i-2*i::6*i-1]=[False]*((n//6-6*i*i+2*i)//(6*i-1)+1)
    if primes1m6[i]:
        primes5m6[6*i*i::6*i+1]=[False]*((n//6-6*i*i)//(6*i+1)+1)
        primes1m6[6*i*i+2*i::6*i+1]=[False]*((n//6-6*i*i-2*i)//(6*i+1)+1)

where for $i>0$

$ p = 6i-1 $ is prime if $ primes5m6 [i] = True $

and

$ p = 6i + 1 $ is prime if $ primes1m6 [i] = True $