I. In-Class Exercises

Programming Exercises

1. Prime Check: L3051
2. Eratosthenes Sieve: L3052
3. Linear Sieve: L3053

II. Knowledge Summary

Core Idea

For natural numbers greater than 1:

• A prime number is divisible only by 1 and itself.
• A composite number is divisible by other natural numbers besides 1 and itself.

Every natural number greater than 1 is either prime or composite. 2 is the smallest prime and also the only even prime.

Prime Testing

To determine whether a number n is prime, it is enough to test divisors up to sqrt(n). If n has a factor larger than sqrt(n), it must also have a corresponding factor smaller than sqrt(n).

1#include<iostream>
2#include<cmath>
3using namespace std;
4
5bool isPrime(int n) {
6    if (n < 2) {
7        return false;
8    }
9
10    int rootN = sqrt(n);
11    for (int i = 2; i <= rootN; i++) {
12        if (n % i == 0) {
13            return false;
14        }
15    }
16    return true;
17}
18
19int main() {
20    int number;
21    cout << "Enter a number: ";
22    cin >> number;
23
24    if (isPrime(number)) {
25        cout << number << " is a prime number." << endl;
26    } else {
27        cout << number << " is not a prime number." << endl;
28    }
29    return 0;
30}

Execution Example

Check whether 29 is prime:

• sqrt(29) ≈ 5.38, so we only test up to 5
• 29 % 2 = 1
• 29 % 3 = 2
• 29 % 4 = 1
• 29 % 5 = 4
• No divisor is found, so 29 is prime

Sieve Methods

Trial division checks one number at a time. If we want all primes in [1, n], doing that repeatedly costs about O(n * sqrt(n)).

A sieve uses the opposite idea: instead of checking numbers one by one, start from known primes and cross out their multiples in batches.

Eratosthenes Sieve

The key observation is:

If p is prime, then all multiples of p (2p, 3p, 4p, ...) are composite.

Important details:

• We only need to sieve up to sqrt(n).
• For a prime i, start crossing out from i * i, because smaller multiples have already been handled by smaller primes.

Steps:

1. Initialize a boolean array of size n + 1 to true.
2. Scan from 2 to sqrt(n).
3. If i is still prime, mark all multiples of i as composite.
4. The remaining true positions are prime numbers.

Time complexity: O(n log log n)
Space complexity: O(n)

1#include<iostream>
2#include<cmath>
3using namespace std;
4
5bool isPrime[105] = {0};
6
7void eratosthenes(int n) {
8    memset(isPrime, 1, sizeof(isPrime));
9    int rootN = sqrt(n);
10    for (int i = 2; i <= rootN; i++) {
11        if (isPrime[i]) {
12            for (int j = i * i; j <= n; j += i) {
13                isPrime[j] = false;
14            }
15        }
16    }
17}
18
19int main() {
20    int n = 0;
21    cin >> n;
22    eratosthenes(n);
23    for (int i = 2; i <= n; i++) {
24        if (isPrime[i]) {
25            cout << i << " ";
26        }
27    }
28    cout << endl;
29    return 0;
30}

Execution Example

Find all primes from 1 to 30:

• i = 2: remove 4, 6, 8, ..., 30
• i = 3: remove 9, 15, 21, 27
• i = 4: already composite, skip
• i = 5: remove 25
• Stop after sqrt(30)

Remaining primes: 2 3 5 7 11 13 17 19 23 29

Euler / Linear Sieve

The linear sieve improves efficiency by ensuring that every composite number is crossed out exactly once, using its smallest prime factor.

Steps:

1. Maintain a boolean array and a list of primes.
2. Scan from 2 to n.
3. If i is prime, add it to the list.
4. For every known prime p, mark i * p as composite.
5. If p divides i, stop immediately.

Time complexity is close to O(n).

1#include <vector>
2#include <iostream>
3using namespace std;
4
5vector<int> primes;
6bool isPrime[105] = {0};
7
8void linearSieve(int n) {
9    memset(isPrime, 1, sizeof(isPrime));
10    for (int i = 2; i <= n; i++) {
11        if (isPrime[i]) {
12            primes.push_back(i);
13        }
14        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
15            isPrime[i * primes[j]] = false;
16            if (i % primes[j] == 0) break;
17        }
18    }
19}
20
21int main() {
22    int n = 0;
23    cin >> n;
24    linearSieve(n);
25    for (int i = 0; i < primes.size(); i++) {
26        cout << primes[i] << " ";
27    }
28    cout << endl;
29    return 0;
30}

Execution Example

For primes in 1 to 20, note that each composite is removed only once:

• 4 is crossed out by 2
• 6 is crossed out by 2
• 9 is crossed out by 3
• 12 is crossed out by 2

That is the reason the linear sieve avoids redundant work.

Problem-Solving Steps

When a problem involves primes:

1. Check one number for primality: use trial division, O(sqrt(n))
2. Find all primes in [1, n]:
   • n <= 10^6: Eratosthenes sieve is enough
   • Larger n: prefer linear sieve
3. Count primes in a range: preprocess with a sieve first
4. Answer many primality queries: sieve once, then query in O(1)

Common Mistakes

• Treating 1 as a prime number
• Using sqrt(n) directly and running into precision issues
• Starting Eratosthenes from i * 2 instead of i * i
• Forgetting the break in the linear sieve
• Allocating an array that is too small

III. Homework

Programming Exercises

1. Prime with k Digits 2: L3054