0
$\begingroup$

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 Eratosthеnes?

Improve this question
$\endgroup$
7
  • $\begingroup$ Possible duplicate of Matrix sieve theorem $\endgroup$
    – Yoav Kallus
    Commented Jun 26, 2019 at 14:53
  • 1
    $\begingroup$ As explained in the linked question, this is more or less equivalent to iterating over all $x, y \equiv \pm 1 \pmod 6$ to eliminate $xy$ as a prime and therefore not a useful alternative to the sieve of Eratosthenes. $\endgroup$
    – Yoav Kallus
    Commented Jun 26, 2019 at 15:17
  • $\begingroup$ In practice proposed algorithm is useful: it allows to calculate primes in the range 10^6 for numbers up to 10^20 for run time <10s on an ordinary laptop.(see link) $\endgroup$
    – Boris Sklyar
    Commented Jun 26, 2019 at 18:58
  • $\begingroup$ there is a much simpler and probably faster method to determine, not which number is prime, but which number is a composite in the arithmetic progression $(6k+1)$ and $(6k-1)$. Once we know which numbers are composite, we can determine which are primes. see answer # 2 here: math.stackexchange.com/questions/549239/… $\endgroup$
    – user25406
    Commented Jun 27, 2019 at 2:13
  • $\begingroup$ If you look closely at arrays A1-A4 then you can see that these arrays are general expression of composite numbers (except divisible by 2 and 3) see [link] (academia.edu/13890086/…) so we are discussing the same method $\endgroup$
    – Boris Sklyar
    Commented Jun 27, 2019 at 8:13

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .