I made this sieve for prime numbers, which I briefly describe:
We consider $\quad p=r+modulus \cdot k \quad$ with $\quad modulus=p_1*p_2* \cdots *p_m$
and then we choose an appropriate reduced residue system $\quad \pmod {modulus} \quad$stored in the vector $\quad Remainder\quad$ of length $\quad \phi (modulus)$, where $ \phi ()$ is Euler's totient function.
Example if $\quad modulus=30\quad $ then$\quad \phi (30) =8 \quad $ and $\quad Remainder = \{-23, -19, -17, -13, -11, -7, -1, 1\}$ is a reduced residue system $\quad \pmod {30}$.
Analyzing the graph to describe the wheel factorization, it can be seen that, excluding $2$, $3$ and $5$, if $\quad p=Remainder[j]+30 \cdot k \quad$ with $k>0$ we can only store the useful areas in gray equal to a matrix with a number of rows equal to $\quad nRow=\phi( 30) =8 $ .
So we choose $modulus<\sqrt n \quad$, $\quad nRow=\phi(modulus)$ and $Remainder[j]<=1$.
To find prime numbers different from $\{p_1, p_2, \cdots ,p_m\}$ and less than $n$ then we use a Boolean array $SIEVE$ of size $nRow * \lceil n/modulus \rceil$, initially all set to $true$, in order to associate the possible residue into each row of the array and so all elements associated with multiples of the prime numbers $\{p_1, p_2, \cdots ,p_m\}$ are not stored.
So we want to get after the sieve that $\quad p=Remainder[j]+modulus \cdot k \quad$ is prime if $\quad SIEVE[j,k]==true$
In traditional sieve of Eratosthenes you can use this pseudocode:
for (p=2; p<sqrt(n); p++)
if ( SIEVE[p] )
for (m=p*p; m<n; m+=p)
SIEVE[m]=false;
if we replace $\quad p*p \quad $ by $\quad (r+modulus \cdot k) \cdot (s+modulus \cdot k) \quad $
where $s$ is a remainder such that $(r \cdot s)\%modulus=t$ and the residue$\quad t \quad$ is the one associated with the row we are using, then we have
$(r+modulus \cdot k) \cdot (s+modulus \cdot k) = (r \cdot s) \% modulus + modulus \cdot [modulus \cdot k \cdot k+k \cdot (r+ s) + \lfloor (r \cdot s)/modulus \rfloor] $
if for each $ t=Remainder[i]$ and for each $r=Remainder[j]$ finding $s=Remainder[x]$ such that $(r \cdot s)\%modulus=t$ then we build two array of size $\quad nRow * nRow \quad$ for the coefficients $C_1$ and $C_2$
and we have $C_1[i,j]=r+ s$
and $C_2[i,j]=\lfloor (r \cdot s)/modulus \rfloor$ if $t=1$ or $r=1$ or $r=t$
or $C_2[i,j]=1+ \lfloor (r \cdot s)/modulus \rfloor$ otherwise
then you can use this pseudocode:
for (k=1; k<=sqrt(n)/modulus; k++)
for (j=0; j<nRow ; j++)
if( SIEVE[j,k] )
for (i=0; i<nRow ; i++)
{
m_min=modulus*k*k + k*C1[i,j] + C2[i,j];
for (m=m_min; m<n/modulus+1; m+=Remainder[j]+modulus*k)
SIEVE[i,m]=false;
}
An improvement obtained is to have numbers smaller than $\quad n/modulus \quad$ and the use of a memory equal to $\quad \phi(modulus)*n/modulus$.
What I noticed is that for $\quad modulus = 2\quad $ then $\quad nRow=1 \quad$ and $\quad m_{min}=2 \cdot k \cdot k + 2 \cdot k \quad $ the sieve is similar to the Sundaram sieve, is there anything like this in the literature?
