Algorithm 3.4 Generating Prime Numbers Part 1
This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.
Learning objectives
- Explain the main ideas and vocabulary in Algorithm 3.4 Generating Prime Numbers Part 1.
- Work through the source examples for Algorithm 3.4 Generating Prime Numbers Part 1 without depending on raw chunk order.
- Use Algorithm 3.4 Generating Prime Numbers Part 1 as selective reference when learner modules point back to How To Solve It By Computers.
Prerequisites
- None curated yet.
Module targets
module-05-problem-solving
AI companion modes
- Explain simply
- Socratic tutor
- Quiz me
- Challenge my understanding
- Diagnose my confusion
- Generate extra practice
- Revision mode
- Connect forward / backward
Source-of-truth note
This unit is anchored to How To Solve It By Computers and the source chapter "Algorithm 3.4 Generating Prime Numbers Part 1". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.
External enrichment
No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.
Source provenance
- Primary source:
How To Solve It By Computers - Source chapter: Algorithm 3.4 Generating Prime Numbers Part 1
- Raw source file:
036-algorithm-3-4-generating-prime-numbers-part-1.md
Merged source
Algorithm 3.4 Generating Prime Numbers Part 1
id: '036-algorithm-3-4-generating-prime-numbers-part-1' book: "How to Solve It by Computer" source_file: "../how-to-solve-it-by-computer-r-g-dromey-for-unit-1.pdf" ocr_source: "../ocr-extracted.txt" chunk_index: 36 chunk_total: 138 title: "Algorithm 3.4 GENERATING PRIME NUMBERS (Part 1)" part: "" chapter: "" pages: start: 126 end: 129 words: 1046
Algorithm 3.4 GENERATING PRIME NUMBERS (Part 1)
Algorithm 3.4 GENERATING PRIME NUMBERS
Problem
Design an algorithm to establish all the primes in the first n positive integers.
Algorithm development
The efficient generation of prime numbers is an open problem. We will
consider here the more restricted Droblem of generating all Drimes in the
first n integers. A prime number is a positive integer that is exactly divisible
only by 1 and itself. The first few primes are:
2357 11 13 17 19 23 29 31 37...
All primes apart from 2 are odd.
a UD
explore how we can establish whether or not a particular number is a prime
number. To do this we can pick a particular example (i.e. the number 13).
The definition of a prime number gives us the start we need. We know that if
the number we are testing is prime it will have no exact divisors other than 1
and itself. This suggests that to determine whether or not 13 is prime we need
t n it 1 n cat Af A <
numbers divide into 13 without remainder we Will know it cannot be prime.
Therefore to test 13 for primality, eleven calls to the mod function are
required. It is easy to see that as n grows, the cost of making these divisions
and tests is going to get very expensive. We must therefore look for ways of
improving the efficiency of our algorithm. A little thought reveals that there
UDO vvv a number of numbers that we have to test for primality and secondly we can try
to improve the efficiency of testing a number for primality.
Following up the first suggestion, we know that apart from 2 we do not
need to examine any of the even numbers. Starting x at 1 and using the
increment
gives us the sequence of numbers
3, 5, 7, 9, 11, 13, 15, 17,...
For Inroe n thiQ Gtill -lenveq with Inroe Get of nnmherq to onnqider fnr
we have eliminated numbers divisible by 2. Cao we extend this to eliminating numbers divisible by 3, 5, and so on? To explore this idea let us first write
down the odd sequence with the multiples of 3 removed. We have:
13 17 19 23 25 29...
Beyond 5 we have the alternating sequence of differences 2, 4. This alternat-
ing difference sequence should be able to be generated. We will not dwell on
it here but it is easv to see that the construct below with dx initiallv 4
abs(dx--6)
has the desired behavior. This device will allow us to eliminate two-thirds of
the numbers from consideration as potential prime numbers candidates.
We might now ask can we eliminate multiples of 5 in a similar manner?
The answer is ves but it would be slightly more involved. This line of attack
u J VV VVV
this however is that one way to generate prime numbers is to simply write
down the list of all integers then cross out multiples of 2, 3, 5, 7, 11, and so
on.
"5 "7 X 9 UT 11
LZ 13 IA 15 1K 17 19
(a) 2 3
(b) 2 3
57 y 11 13 17
19
multiples of 3 crossed out
(c) 2
57 11
3 13 17 19
At stage (c) in this instance we are left with all prime numbers less than
- If we start out with a much larger list and successively cross out multiples
of 2, 3, 5, 7, 11,...
the numbers that are not crossed out will be prime
numbers. This idea for generating primes dates back to the early Greek
mathematician, Eratosthenes and is usually referred to as the "sieve of
Era tncthpnpc
There is a problem in implementing this method directly if it is neces-
sary to generate a large number of primes. Storage proportional to the span of integers up to n may be required.
Further investigation of the "crossing out" mechanism indicates that for
large n most elements are crossed out a number of times (e.g. 15 is crossed
it nnnlt;nlp nf nna m Ill tinle of
These observations suggest that it is worth while trying to see if there is
any way in which we can cut down on the amount of storage and testing needed to find a set of primes.
We have previously seen that to determine that 13 is a prime it would
need to be divided by the set of numbers 2, 3, 4,
11, 12. Studying this
mechaniqm enref"llv nnd notino how the qenrrh for the qmnlleqt diviqnr of
1numoer was terminated (algorithm 3.2) we can see that It IS not necessary to
test divisors beyond I V 131. If a number x has an exact divisor then there will
have to be a factor less than or equal to V x. (See the reasoning in algorithm
3.2 for an explanation of this.) For large x termination of the divisor testing
at Vx will be a relatively efficient operation (e.g. when x is approximately
1000, division by only the primes up to 31 is all that is needed to test x for
primality--this Involves only divisions). Division by composite numbers
is never needed because if a composite number is an exact divisor, this
implies that a smaller prime factor of the composite has already been an
exact divisor.
At this stage we can Drooose a basic structure for our algorithm:
while x<n do
begin
(a) abs(dx 6), generate next x using the construct dx
(b) test whether x is prime using all primes S/ x,
If f ru-nA
later testing against larger x values.
end
To test all integers up to n for primality we will need to retain all primes up to
Every time a new x is brought up for testing we will need to ensure that
we have the appropriate set of primes to divide into x.
Y vnn OD nv7Yi-1D
2,357
Our method for generating x values excludes all multiples of 2 and 3.
Therefore our method for generating x values will produce only primes for
values of x less than 25. As soon as x reaches 25 the divisor 5 will need to be