python教程

Euler’s sieve

Eric Martin, CSE, UNSW

COMP9021 Principles of Programming, session 2, 2018

In [2]: from math import sqrt

from timeit import timeit

from itertools import zip_longest

import matplotlib.pyplot as plt

With Eratosthenes’ sieve, a number can be crossed out more than once. For instance, in case n ≥ 12, 12

will be crossed out as a multiple of 2 and then as a multiple of 3. Euler’s sieve works with a list of numbers

2

most equal to n.

• e next member of the resulting list should contain 3; multiplying 3 with 3 and the following

members of the list up to and excluding the rst number greater than b

multiples of 3 at most equal to n that remain, namely, those that are not multiple of 2.

• e next member of the resulting list should contain 5; multiplying 5 with 5 and the following

members of the list up to and excluding the rst number greater than b

sieve = list(range(2, n + 1))

In [4]: def print_sieve_contents():

print(f'{p:3}', end = '')

print_sieve_contents()

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

To observe how, with n set to 25, proper multiples of 2 are crossed out, we call the following function

with i set to 0 as argument.

1

In [5]: def eliminate_proper_multiples(i):

sieve.remove(factor)

j += 1

else:

break

In [6]: eliminate_proper_multiples(0)

print_sieve_contents()

Now eliminating proper multiples of 2

Eliminating 2 * 2 = 4

Eliminating 2 * 3 = 6

Eliminating 2 * 5 = 10

We see the aw. Having rst eliminated 2 ×2, 4 is not longer in the list, which prevents 8 from being

eliminated, and the same holds for other multiples of 2.

is suggests to, for an arbitrary value of n, amend the procedure as follows.

• using 2, the rst number in the list:

– remove 2

2

, 2

3

, 2

4

– remove 2 × 3, 2

× 3, 2

3

× 3, …, up to 2

r

× 3 for the largest r with 2

r

× 3 ≤ n,

– as 4 is no longer in the list, remove 2 × 5, 2

2

×5, 2

3

– as 8 is no longer in the list, remove 2 × 9, 2

2

×9, 2

3

– …

• using 3, the next number in what remains of the list:

– remove 3

2

, 3

3

, 3

4

– as 4 is no longer in the list, remove 3 × 5, 3

2

×5, 3

3

2

– as 8, 9 and 10 are no longer in the list, remove 3 × 11, 3

× 11, 3

× 11, …., up to 3

r

× 11 for

r

• …

We stop when the next number in what remains in the list exceeds b

√

nc.

Let us verify that the procedure is correct. At stage k, all proper multiples of the kth prime number

k

at most equal to n are removed from the list. is is veried by induction. Indeed, if during stage k, a

number m in {2, 3, . . . , n} with p

k

removed from the list during one of the previous stages,

• or m is greater than p

k

but no longer belongs to the list (it is a number such as 4, 6, 8 at stage 1, or

a number such as 4, 6, 8, 9, 10 at stage 2), in which case:

– either m was removed during one of the previous stages, hence m is a multiple of at least one

1

k−1

– or m is a multiple of p

r+1

k

To observe how, with n set to 25, nonzero powers of 2 times 2, 3, 5, 7, 9 and 11, nonzero powers of 3

times 3, 5 and 7, and nonzero powers of 5 times 5 are eliminated, the following function is successively

called with i set to 0 and k set to 0, 1, 2, 3, 4 and 5 as arguments, then with i set to 1 and k set to 0, 1 and

2 as arguments, then with i set to 2 and k set to 0 as arguments.

In [7]: def eliminate_proper_multiples(i, k):

print(' Eliminating '

)

sieve.remove(factor)

factor *= sieve[i]

power += 1

3

In [8]: sieve = list(range(2, n + 1))

4