Return to Question

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]+modulus \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$ 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 pseusocode:

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 $r$ and for each $t$ finding $s$ such that $(r \cdot s)\%modulus=t$ then we build two array of size $\quad nRow \cdot nRow \quad$ for the coefficients $C_1$ and $C_2$

and we have $C_1(t,r)=r+ s$

and $C_2(t,r)=\lfloor (r \cdot s)/modulus \rfloor$ if $t=1$ or $r=1$ or $r=t$

or $C_2(t,r)=1+ \lfloor (r \cdot s)/modulus \rfloor$ otherwise

then you can use this pseusocode:

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?

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?

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]+modulus \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$ 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 pseusocode:

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 $r$ and for each $t$ finding $s$ such that $(r \cdot s)\%modulus=t$ then we build two array of size $\quad nRow \cdot nRow \quad$ for the coefficients $C_1$ and $C_2$

and we have $C_1(r,t)=r+ s$

and $C_2(r,t)=\lfloor (r \cdot s)/modulus \rfloor$ if $t=1$ or $r=1$ or $r=t$

or $C_2(r,t)=1+ \lfloor (r \cdot s)/modulus \rfloor$ otherwise

then you can use this pseusocode:

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?

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]+modulus \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$ 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 pseusocode:

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 $r$ and for each $t$ finding $s$ such that $(r \cdot s)\%modulus=t$ then we build two array of size $\quad nRow \cdot nRow \quad$ for the coefficients $C_1$ and $C_2$

and we have $C_1(t,r)=r+ s$

and $C_2(t,r)=\lfloor (r \cdot s)/modulus \rfloor$ if $t=1$ or $r=1$ or $r=t$

or $C_2(t,r)=1+ \lfloor (r \cdot s)/modulus \rfloor$ otherwise

then you can use this pseusocode:

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?

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]+modulus \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 $ .

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$ 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 pseusocode:

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 $r$ and for each $t$ finding $s$ such that $(r \cdot s)\%modulus=t$ then we build two array of size $\quad nRow \cdot nRow \quad$ for the coefficients $C_1$ and $C_2$

and we have $C_1(r,t)=r+ s$

and $C_2(r,t)=\lfloor (r \cdot s)/modulus \rfloor$

or $C_2(r,t)=1+ \lfloor (r \cdot s)/modulus \rfloor$ if $t=1$ or $r=1$ or $r=t$

then you can use this pseusocode:

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?

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]+modulus \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$ 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 pseusocode:

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 $r$ and for each $t$ finding $s$ such that $(r \cdot s)\%modulus=t$ then we build two array of size $\quad nRow \cdot nRow \quad$ for the coefficients $C_1$ and $C_2$

and we have $C_1(r,t)=r+ s$

and $C_2(r,t)=\lfloor (r \cdot s)/modulus \rfloor$ if $t=1$ or $r=1$ or $r=t$

or $C_2(r,t)=1+ \lfloor (r \cdot s)/modulus \rfloor$ otherwise

then you can use this pseusocode:

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?