The new algorithm of the sieve for finding all prime numbers
up to a specified integer

Yuji Tanose

ABSTRACT

The Sieve of Eratosthenes is a simple ancient algorithm for finding
all prime numbers up to a specified integer.
This time, I found the algorithm of the sieving which is　different
from this way. It is the algorithm that can sieve the answers of the
product among the prime numbers easily from the sets of the prime
numbers and the answers of the product among the prime numbers up to a
specified integer.

1.　INTRODUCTION

Dirichlet's theorem on arithmetic progressions states that for any two
positive coprime integers a and d, there are infinitely many primes of
the form a＋nd, where n ≧0. It is known as the example that two
infinite sequences of numbers with common difference are important
among them. They are infinite sequences of numbers with common
difference that the common difference is 6 at 5 in the first term and
the common difference is 6 at 7 in the first term. That these two
sequences contain all prime numbers and the answers of the product
among the prime numbers exclude 2 and 3 of the prime is known. It
becomes following congruence when showing these two sequences by a
numerical formula.

  S≡±１（mod 6）

（S: Sets of all prime numbers and the answers of the product among the
prime numbers exclude 2 and 3 of the prime）

Then, I found the algorithm that sieves only the answers of the
product among the prime numbers from sets of all prime numbers and the
answers of the product among the prime numbers exclude 2 and 3 of the
prime up to a specified integer. And new algorithm for finding all
prime numbers up to a specified integer is structured by the
congruence too.

2.　ALGORITHM

It becomes following congruence to sieve only the answers of the
product among the prime numbers from the answers of congruence,S≡±１
（mod 6）.

  N≡±5(mod (5×6) ) 　　 ,where N ≧5²
  N≡±7(mod (7×6) )　　  ,where N ≧7²
  N≡±11(mod (11×6) )　 ,where N ≧11²
                       ⋮
  N≡±Pｎ(mod (Pｎ×6) ) ,where N ≧Pｎ²

(N: Set of the answers of product among the prime numbers that have to
sieve up to a specified integer)
(Pｎ: prime number which appear “n”th from prime 5 )

Then it shows the algorithm that sieves only the answers of the
product among the prime numbers from sets of all prime numbers and the
answers of the product among the prime numbers exclude 2 and 3 of the
prime less than or equal to given integer 100 for example by new
method.

  1.　Create a list of the prime numbers and the answers of the product
among the prime numbers from 5 to 100 by the congruence, S≡±１（mod 6）.

  2.　Sieve from the list all answers of the congruence,
  N≡±5(mod(5×６)) ,where 5²≦N ≦100

  3.　Sieve from the list all answers of the congruence,
  N≡±7(mod(7×６)) ,where 7²≦N ≦100

  4.　As 11²>100 , stop to sieve.

  5.　All the remaining numbers on the list are prime.

3.　EXAMPLE

To find all the prime numbers exclude 2 and 3 of the prime less than
or equal to 100,proceed as follows:

  1. Create a list of the prime numbers and the answers of the product
among the prime numbers from 5 to 100 by the congruence, S≡±１（mod 6）.

  5 11 17 23 29 35 41 47 53 59 65 71 77 83 89 95
  7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97

  2. Sieve from the list all answers of the congruence,
  N≡±5(mod(5×６)) ,where 5²≦N ≦100

  5 11 17 23 29  ・ 41 47 53 59  ・ 71 77 83 89  ・
  7 13 19  ・ 31 37 43 49  ・ 61 67 73 79  ・ 91 97

  3. Sieve from the list all answers of the congruence,
  N≡±7(mod(7×６)) ,where 7²≦N ≦100

  5 11 17 23 29  ・ 41 47 53 59  ・ 71  ・ 83 89  ・
  7 13 19  ・ 31 37 43  ・   ・ 61 67 73 79  ・   ・ 97

  4. As 11² >100 , stop to sieve.

  5. All the remaining numbers on the list are prime exclude 2 and 3
of the prime.

  5 11 17 23 29  ・ 41 47 53 59  ・ 71  ・ 83 89  ・
  7 13 19  ・ 31 37 43  ・   ・ 61 67 73 79  ・   ・ 97

4. Remarks

The process to find the congruence, N≡±Pｎ(mod (Pｎ×6) ).

The all answers of product among the prime numbers exclude 2 and 3 can
be shown by the　following numerical formula.

３０K＋２５, ３０K＋３５, ４２K＋４９, ４２K＋７７, ６６K＋１２１,
６６K＋１４３, ７８K＋１６９, ７８K＋２２１, …

(K : the positive integer that begins with 0.)

I attempted to rewrite a numerical formula as follows to ascertain law
among these numerical formulas.

３０K＋２５　＝（５×６）K＋（５×５）
３０K＋３５　＝（５×６）K＋（５×７）
４２K＋４９　＝（７×６）K＋（７×７）
４２K＋７７　＝（７×６）K＋（７×11）
６６K＋１２１＝（11×６）K＋（11×11）
６６K＋１４３＝（11×６）K＋（11×13）
７８K＋１６９＝（13×６）K＋（13×13）
７８K＋２２１＝（13×６）K＋（13×17）
…
Then I found the numerical formula,N≡±Pｎ(mod (Pｎ×6) ).