Lab 08 Examples (Sieve of Eratosthenes and Euclid's Algorithm)¶
Click <shift> <enter> in each code cell to run the code. Be sure to start with the #include directives to load the required libraries.
// For Lab 08, we are limited to using only <iostream> and <string>
#include <iostream>
#include <string>
Sieve of Eratosthenes¶
A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. In other words, a prime number has exactly two distinct positive divisors: 1 and itself.
7 is prime because its only divisors are 1 and 7.
8 is not prime because it can be divided evenly by 2 and 4 in addition to by 1 and 8.
9 is not prime because it can be divided evenly by 3 in addition to by 1 and 9.
The basic method to test whether a number is prime is to try dividing it by all integers from 2 up to the square root of the number. If none of these divisions results in a quotient with a remainder of zero, then the number is prime.
To test whether 29 is prime, we would try dividing it by 2, 3, 4, and 5 (the integers up to the square root of 29, which is about 5.39). Since none of these divisions results in a quotient with a remainder of zero, we conclude that 29 is prime.
| Divisor | Quotient (⌊29 / d⌋) | Remainder (29 % d) | Divides? |
|---|---|---|---|
| 2 | floor(29 / 2) = 14 | remainder(29 / 2) = 1 | No |
| 3 | floor(29 / 3) = 9 | remainder(29 / 3) = 2 | No |
| 4 | floor(29 / 4) = 7 | remainder(29 / 4) = 1 | No |
| 5 | floor(29 / 5) = 5 | remainder(29 / 5) = 4 | No |
Since none of the divisions produce a remainder of 0, the number 29 is prime.
The Sieve of Eratosthenes is a more efficient algorithm to find all prime numbers up to a specified integer n. It works by iteratively marking the multiples of each prime number starting from 2.
Consider the n = 30. We start with a list of all integers from 2 to 30:
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
We begin with the first number in the list, which is 2. We mark all multiples of 2 (except 2 itself) as non-prime: (yellow highlight indicates non-prime numbers)
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
Next, we move to the next unmarked number, which is 3. We mark all multiples of 3 (except 3 itself) as non-prime:
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
We continue this process with the next unmarked number, which is 5, and mark all multiples of 5 (except 5 itself) as non-prime:
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
We can stop the process when we reach the square root of n (approximately 5.48 for n = 30). The remaining unmarked numbers in the list are all prime:
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
Euclid's Algorithm¶
The greatest common divisor (GCD) of two integers is the largest positive integer that divides both numbers without leaving a remainder.
Example: GCD of 8 and 12¶
We want to find the GCD of 8 and 12. Let's check which numbers divide both:
| Check 12 ÷ d | Check 8 ÷ d |
|---|---|
| 12 ÷ 8 = 1 remainder 4 | 8 ÷ 8 = 1 remainder 0 |
| 12 ÷ 7 = 1 remainder 5 | 8 ÷ 7 = 1 remainder 1 |
| 12 ÷ 6 = 2 remainder 0 | 8 ÷ 6 = 1 remainder 2 |
| 12 ÷ 5 = 2 remainder 2 | 8 ÷ 5 = 1 remainder 3 |
| 12 ÷ 4 = 3 remainder 0 | 8 ÷ 4 = 2 remainder 0 |
The largest number that divides both is 4.
Instead of checking all divisors, we can use the Euclidean algorithm:
- 12 ÷ 8 = 1 remainder 4
- 8 ÷ 4 = 2 remainder 0
Since the last non-zero remainder is 4, the GCD of 8 and 12 is 4.
Example: GCD of 1528 and 440¶
Apply Euclid's algorithm:
- 1528 ÷ 440 = 3 remainder 208
- 440 ÷ 208 = 2 remainder 24
- 208 ÷ 24 = 8 remainder 16
- 24 ÷ 16 = 1 remainder 8
- 16 ÷ 8 = 2 remainder 0
The last non-zero remainder is 8, so the GCD of 1528 and 440 is 8.
Least Common Multiple (LCM)¶
The least common multiple (LCM) of two integers a and b is the smallest positive integer divisible by both.
Example: LCM of 6 and 8¶
We use the formula:
$$ \text{LCM}(a, b) = \frac{a \cdot b}{\text{GCD}(a, b)} $$
For a = 6, b = 8, and GCD(6, 8) = 2:
$$ \text{LCM}(6, 8) = \frac{6 \cdot 8}{2} = \frac{48}{2} = 24 $$
Relatively Prime¶
A group of numbers is relatively prime if the greatest common divisor (GCD) of the entire group is 1.
Example — Relatively Prime (GCD = 1)¶
- Numbers: 6, 10, 15
- Step 1: GCD(6, 10) = 2
- Step 2: GCD(2, 15) = 1
- Group GCD = 1 → The numbers are relatively prime
Example — Not Relatively Prime (GCD > 1)¶
- Numbers: 6, 10, 14
- Step 1: GCD(6, 10) = 2
- Step 2: GCD(2, 14) = 2
- Group GCD = 2 → The numbers are not relatively prime
General Rule¶
To compute the GCD of multiple numbers:
$$ \mathrm{GCD}(a, b, c) = \mathrm{GCD}(\mathrm{GCD}(a, b), c) $$