Skip to main content
MathOverflow

Return to Question

edited body
Source Link
Boris Sklyar
Boris Sklyar
  • 11
  • 1
  • 7

My question is: Does proposed "matrix sieve" algorithm suitable as an alternative for sieve of EratosphenesEratosthеnes?

My question is: Does proposed "matrix sieve" algorithm suitable as an alternative for sieve of Eratosphenes?

My question is: Does proposed "matrix sieve" algorithm suitable as an alternative for sieve of Eratosthеnes?

Source Link
Boris Sklyar
Boris Sklyar
  • 11
  • 1
  • 7

Matrix sieve algorithm

I proposed "matrix sieve" algorithm for finding primes as two pairs of 2-dimensional arrays: positive integers which do not appear in these arrays are indexes $k$ of primes in the sequences $S1(k)=6k-1$ and $S2(k)=6k+1$.

Positive integers which do not appear in both arrays $ A1(i,j)=6i^2 + (6i-1)(j-1)$ and $A2(i,j)=6i^2 + (6i+1)(j-1)$

                            |  6   11    16     21   ...|
                A1(i,j) =   | 24   35     46    57   ...|
                            | 54   71     88   105   ...|
                            | 96  119    142   165   ...|
                            |...  ...  ...   ...     ...|


                             |  6    13   20    27   ...|
                 A2(i,j) =   | 24    37   50    63   ...|
                             | 54    73   92   111   ...|
                             | 96   121  146   171   ...|
                             |...      ...       ...        ...   ...|

are indexes $k$ of primes in the sequence $S1(k)=6k-1$ .

Positive integers which do not appear in both arrays $ A3(i,j)=6i^2-2i + (6i-1)(j-1)$ and $A4(i,j)=6i^2 +2i+ (6i+1)(j-1)$

                                   | 4       9     14       19.. |
                                   |20      31     42       53...|
                                   |48      65     82       99...|
                          A3(i,j)= |88     111     134     157...|
                                   |...   ...      ...     ...   |

                            | 8      15      22     29 ..|
                            |28     41       54     67...|
                   A4(i,j)= |60     79       98     117..|
                            |104   129      154    179...|
                            |...    ...     ...     ...  |

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

My question is: Does proposed "matrix sieve" algorithm suitable as an alternative for sieve of Eratosphenes?