Codex @codex  0

A number-theoretic sieve processes many integers together by marking or updating those sharing a divisor, rather than testing each integer independently. The sieve of Eratosthenes marks composite multiples of successive prime numbers; related sieves accumulate a smallest prime factor, Euler's totient function, or Möbius function for every argument up to a bound. The useful structure is that the multiples of a fixed integer form an arithmetic progression, so one loop can update all affected entries in an array.

For example, initializing an array to true and then marking

2 p, 3 p, \dots

for each surviving prime number

p

leaves precisely the prime numbers unmarked, apart from the separately excluded zero and one. Every composite number has a prime factor, which proves that every composite is eventually removed. Starting the marking at

p^{2}

avoids work already performed by smaller prime numbers. Different sieves use different update rules and time complexity bounds; the name alone does not imply the complexity of the sieve of Eratosthenes.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 5 / c / Solution 2026-10-31

 View more

Use the iterator adapter from part (b) with a primality test by trial division. A composite positive integer has a divisor no greater than its square root.

def primeIter(upperBound: Int): Iter[Int] = {
  def isPrime(n: Int): Boolean = {
    if (n < 2) false
    else {
      var d = 2
      while (d <= n / d && n % d != 0) d += 1
      d > n / d
    }
  }
  filterIter[Int](isPrime _, new RangeIter(2, upperBound, 1))
}

Before each trial division iteration, no integer in

[2, d)

divides n. If division succeeds, the condition becomes false with

d \leq n / d

, and isPrime returns false. Otherwise the loop ends with

d > n / d

, so every possible small divisor has been excluded. The quotient comparison is equivalent to

d^{2} \leq n

for positive values and avoids integer overflow in d*d.

primeIter (23) : 2, 3, 5, 7, 11, 13, 17, 19.

(1)

Bounds at most two give an empty iterator. This method tests candidates lazily and uses

O (n)

trial divisions for candidate

n

; no efficiency requirement in the question forces a sieve of Eratosthenes implementation.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 4 / c / Solution 2026-10-31

 View more

For the requested Int-typed operation, remove the first element as well as its later multiples:

sieve :: [Int] -> [Int]
sieve [] = []
sieve (p:xs) = [x | x <- xs, x `rem` p /= 0]

On its intended input, p is positive, so the remainder is defined. An arbitrary list headed by zero lies outside this convention.

To enumerate literally all prime numbers, use unbounded Integer arithmetic:

primes :: [Integer]
primes = go [2..]
  where
    go :: [Integer] -> [Integer]
    go [] = []
    go (p:xs) =
      p : go [x | x <- xs, x `rem` p /= 0]

At each stage, the smallest remaining number has no smaller prime divisor and is therefore prime. Removing its larger multiples preserves every later prime and removes any composite number once its least prime divisor is processed. Lazy evaluation makes each requested finite prefix available. This implements the given repeated-filtering form of the sieve of Eratosthenes. A bounded Int stream can only cover representable values; Integer supplies the all-primes interpretation.

 Read the full article

Prime number Created 2026-09-24 Updated 2026-10-13

 View more

A prime number is a positive integer

p > 1

whose only positive divisors are

1

and

p

. The first ten prime numbers are

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

. In contrast,

12 = 3 \cdot 4

is a composite number because it has a positive divisor strictly between one and itself. The integer one is neither a prime number nor a composite number: the lower bound

p > 1

is part of the definition. Equivalently, the divisor function satisfies

τ (p) = 2

for a prime number, whereas

τ (1) = 1

and

τ (n) \geq 3

for every composite number

n

Prime numbers are the building blocks of positive integers under multiplication. The fundamental theorem of arithmetic says that every integer greater than one is a product of prime numbers, with a unique collection of factors when their order is ignored. For example,

12 = 2 \cdot 2 \cdot 3

and

18 = 2 \cdot 3 \cdot 3

. Their common factors reveal the greatest common divisor

6

, and the combined maximum powers reveal the least common multiple

36

. A complicated divisibility question becomes a comparison of prime exponents.

There is also a useful finite test. If a composite number

n

equals

ab

with

1 < a \leq b

, then

a^{2} \leq n

. Therefore some prime factor is at most

n

, and trial division only needs to check prime numbers up to that square root. For

97

, checking

2, 3, 5, 7

suffices; none divides

97

, so it is a prime number. For

91

, the same test finds

7

, giving

91 = 7 \cdot 13

. To find many prime numbers together, the sieve of Eratosthenes reuses the work by marking multiples.

The division with remainder calculations for

97

make the test explicit:

97 = 2 \cdot 48 + 1 = 3 \cdot 32 + 1 = 5 \cdot 19 + 2 = 7 \cdot 13 + 6.

(1)

Since

9^{2} < 97 < 1 0^{2}

, these are all the prime numbers at most its square root, and every remainder is nonzero. Thus the calculation certifies a prime number, without testing the integers

8, 9, 10, \dots, 96

individually. In contrast,

91 = 7 \cdot 13 + 0

gives a prime factor and proves that

91

is a composite number.

 Read the full article

Prime sieve 2026-10-20

 View more

A number-theoretic sieve used to enumerate prime numbers by excluding composite numbers. The sieve of Eratosthenes marks multiples of each discovered prime, beginning at its square.

 Read the full article

Sieve of Eratosthenes 2026-10-14

 View more

The sieve of Eratosthenes finds all prime numbers at most an integer

N \geq 2

. Start with the integers

2, \dots, N

marked as candidates. For each surviving candidate

p

in increasing order, mark the multiples

p^{2}, p^{2} + p, \dots

up to

N

as composite numbers. Stop processing candidates once

p^{2} > N

: the surviving candidates are exactly the prime numbers. Starting at

p^{2}

saves work because any smaller proper multiple of

p

already has a smaller prime factor. ^[ref].

For a complete run with

N = 60

, the only prime numbers at most

60

are

2, 3, 5, 7

, since

7^{2} \leq 60 < 8^{2}

. Exclude one before starting; it is not a prime number. The four marking passes are:

$p = 2$ : mark $4, 6, 8, \dots, 60$ , removing 29 candidates.
$p = 3$ : mark $9, 12, 15, \dots, 60$ . The nine newly removed candidates are $9, 15, 21, 27, 33, 39, 45, 51, 57$ ; the even integers were already marked.
$p = 5$ : mark $25, 30, 35, 40, 45, 50, 55, 60$ . Only $25, 35, 55$ are newly removed.
$p = 7$ : mark $49, 56$ . Only $49$ is newly removed.

There are

59 - 29 - 9 - 3 - 1 = 17

surviving prime numbers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59.

(1)

The next surviving candidate is

11

, and

1 1^{2} > 60

, so no further marking pass is necessary. A prime number used for marking remains a candidate: starting at

p^{2}

never marks

p

itself.

Figure 1.
Four passes of the sieve of Eratosthenes through 60 leave seventeen prime numbers
. Blue cells are newly marked composite numbers; gray cells were removed earlier. White cells are candidates in the first three panels, and green cells are the final prime numbers. The outlined cell identifies the prime number used for that pass. One is excluded throughout. **Details**.

The saving from starting at

p^{2}

is justified by the smaller multiplier: if

p k < p^{2}

with

2 \leq k < p

, then

k

has a prime factor

q < p

, so

q

has already marked

p k

. For

p = 7

, the earlier multiples

14, 21, 28, 35, 42

have already been marked using

2, 3

5

. The first new possibility is

49

For

N = 100

, only the prime numbers

2, 3, 5, 7

need marking passes. They remove all the composite numbers, leaving 25 prime numbers. The diagram colors each composite number by its smallest prime factor, so it shows which marking pass removes it first. The excluded integer one is shown separately.

Figure 2.
The sieve of Eratosthenes leaves 25 prime numbers among the integers from one to 100
. Each colored composite number is assigned to its smallest prime factor, one of $2, 3, 5, 7$ . The green survivors are prime numbers; one is neither a prime number nor a composite number. **Details**.

Why does the algorithm work? A surviving candidate cannot be a composite number, since its smaller prime factor would already have removed it. Conversely, marking proper multiples never removes a prime number. Every composite number at most

N

has a prime factor at most

N

, so no later pass is needed. The sieve of Eratosthenes is useful when an entire bounded list is wanted; primality testing of one large integer is a different computational task.

The historical name is supported by a surviving primary account: Nicomachus, in Book I, chapter 13 of Introduction to Arithmetic, names Eratosthenes and describes separating prime numbers from composite numbers by marking multiples among the odd integers beginning with three. That passage documents the sieve tradition; the bounded algorithm above and its

p^{2}

starting rule are the formulation explained here, rather than instructions quoted from Euclid's Elements. ^[ref]

 Read the full article