Project Nayuki


The versatile sieve of Eratosthenes

Introduction

The sieve of Eratosthenes is an efficient algorithm to mark whether each integer between 0 to n is prime. It turns out that the algorithm is useful for calculating other interesting values that are also based on the prime factorization of a number.

This page will show how the basic sieve of Eratosthenes can be modified to calculate other number-theoretic functions. A prior understanding of the basic algorithm will be assumed (please browse other resources for an introduction).

Designing and applying these modified forms of the sieve of Eratosthenes has been very helpful in a number of my Project Euler solution implementations.

Technical notes

The sieve of Eratosthenes (and its variants) takes an upper limit integer n, and computes a table of some particular number-theoretic function f(k) for every value of k from 0 to n. Hence if you wish to evaluate f(k) for many values of k between 0 and n (i.e. the usage is dense), then it helps to run a sieve first to pre-compute all the values in that domain. If the queries of k are sparse however (e.g. only testing if a couple of numbers are prime), then sieving is not efficient in time or memory.

All code examples are given in the Python programming language, for clarity and to avoid issues with integer overflow. These algorithms can certainly be implemented in languages with fixed-width integer types (such as C/C++/C#/Java/JavaScript), but extreme care must be taken to prove that every calculation does not overflow the chosen integer type’s range.

Each example sieving function takes a non-negative integer named limit and returns a list/array of limit+1 elements (usually integers). Then, for any query number k in the range 0 <= k <= limit, the expression result[k] gives the value of the desired number-theoretic function.

Most number-theoretic functions don’t have a meaningful or consistent definition at 0 or 1. But because Python arrays start at index 0, I made an earnest attempt to give sensible values to indexes 0 and 1. For the most part, you can ignore these first two values, and only consider values starting at index 2.

Source code

License: Project Nayuki hereby places all code on this page regarding the sieve of Eratosthenes in the public domain. Retaining the credit notice containing the author and URL is encouraged but not required.


Primeness (the basic sieve)

def sieve_primeness(limit):
    result = [True] * (limit + 1)
    result[0] = False
    result[1] = False
    for i in range(2, len(result)):
        if result[i]:
            for j in range(i * i, len(result), i):
                result[j] = False
    return result

isPrime(k) is true if k is a prime number; otherwise it’s false if k is 0 or 1 or composite.

Table of example values:

k isPrime(k)
0false
1false
2true
3true
4false
5true
6false
7true
8false
9false
10false
11true
12false
13true
14false
15false
16false
17true
18false
19true
20false
21false
22false
23true
24false
25false
26false
27false
28false
29true
30false

Smallest prime factor

def sieve_smallest_prime_factor(limit):
    result = [0] * (limit + 1)
    result[1] = 1
    for i in range(2, len(result)):
        if result[i] == 0:
            result[i] = i
            for j in range(i * i, len(result), i):
                if result[j] == 0:
                    result[j] = i
    return result

smallestPrimeFactor(k) is the smallest integer p such that p is greater than 1 and p divides k. The smallest proper divisor is necessarily a prime number.

When given a composite number k, we can repeatedly divide out its smallest prime factor in order to obtain its prime factorization.

Table of example values:

k smallestPrimeFactor(k)
00
11
22
33
42
55
62
77
82
93
102
1111
122
1313
142
153
162
1717
182
1919
202
213
222
2323
242
255
262
273
282
2929
302

Notice that smallestPrimeFactor(k) = k if and only if k is a prime number. Hence, this information can be viewed as a richer version of the plain sieve of Eratosthenes (which only gives a Boolean value per number).

Totient function

def sieve_totient(limit):
    result = list(range(limit + 1))
    for i in range(2, len(result)):
        if result[i] == i:
            for j in range(i, len(result), i):
                result[j] -= result[j] // i
    return result

totient(k) (or φ(k)) is defined as the number of integers in the range [1, k] that are coprime with k. This value is useful for modular arithmetic.

Table of example values:

k totient(k)
00
11
21
32
42
54
62
76
84
96
104
1110
124
1312
146
158
168
1716
186
1918
208
2112
2210
2322
248
2520
2612
2718
2812
2928
308

Notice that totient(k) = k−1 if and only if k is a prime number. Hence, this information can be viewed as a richer version of the plain sieve of Eratosthenes (which only gives a Boolean value per number).

Omega function

def sieve_omega(limit):
    result = [0] * (limit + 1)
    for i in range(2, len(result)):
        if result[i] == 0:
            for j in range(i, len(result), i):
                result[j] += 1
    return result

omega(k) (or ω(k)) is defined as the number of distinct prime factors that k has.

Table of example values:

k omega(k)
00
10
21
31
41
51
62
71
81
91
102
111
122
131
142
152
161
171
182
191
202
212
222
231
242
251
262
271
282
291
303

Note that for a given m, the smallest k such that omega(k) = m is given by k = primorial(m). Furthermore the function grows rather slowly, because omega(k) ≤ log2(k).

Radical function

def sieve_radical(limit):
	result = [1] * (limit + 1)
	result[0] = 0
	for i in range(2, len(result)):
		if result[i] == 1:
			for j in range(i, len(result), i):
				result[j] *= i
	return result

radical(k) is defined as the product of the unique prime factors of k.

Table of example values:

k radical(k)
00
11
22
33
42
55
66
77
82
93
1010
1111
126
1313
1414
1515
162
1717
186
1919
2010
2121
2222
2323
246
255
2626
273
2814
2929
3030

Notice that radical(k) = k if and only if k is square-free.