Unit 2: Primality Testing

Opening Hook — The Invisible Math Guarding Your Money

Learning Outcomes — Bloom's Taxonomy Mapped

Concept Explanation — Primality Testing from Scratch

1. Introduction to Primality Testing

What is a prime number? A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Note that 2 is the only even prime. Every even number greater than 2 is divisible by 2, so it cannot be prime. Also, 1 is NOT prime by convention (it has only one divisor, not two).

Naive O(n) Primality Test

The simplest approach: check if any number from 2 to n-1 divides n. If yes, n is not prime.

C++
// Naive primality test — O(n) time complexity
#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    if (isPrime(n))
        cout << n << " is PRIME" << endl;
    else
        cout << n << " is NOT prime" << endl;
    return 0;
}

Python
# Naive primality test — O(n) time complexity
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

n = int(input("Enter a number: "))
if is_prime(n):
    print(f"{n} is PRIME")
else:
    print(f"{n} is NOT prime")

2. O(√n) Optimized Primality Test

Key Insight: If n = a × b where both a and b are greater than √n, then a × b > √n × √n = n, which is a contradiction. Therefore, if n has any factor other than 1 and itself, at least one factor must be ≤ √n.

C++
// O(√n) primality test — optimized
#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

int main() {
    int n;
    cout << "Enter number: ";
    cin >> n;
    cout << n << (isPrime(n) ? " is PRIME" : " is NOT prime") << endl;
    return 0;
}

Python
# O(√n) primality test — optimized with 6k±1 trick
def is_prime(n):
    if n <= 1: return False
    if n <= 3: return True
    if n % 2 == 0 or n % 3 == 0: return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

3. Factorization of a Number

Trial division finds all prime factors by repeatedly dividing by the smallest possible factor. The optimized approach runs in O(√n) time.

C++
// Find ALL prime factors of n — O(√n)
#include <iostream>
#include <vector>
using namespace std;

vector<int> primeFactors(int n) {
    vector<int> factors;
    while (n % 2 == 0) {
        factors.push_back(2);
        n /= 2;
    }
    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 1) factors.push_back(n);
    return factors;
}

int main() {
    int n = 84;
    auto f = primeFactors(n);
    cout << "Prime factors of " << n << ": ";
    for (int x : f) cout << x << " ";
    return 0;
}

Python
# Find ALL prime factors of n — O(√n)
def prime_factors(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n //= i
        i += 2
    if n > 1:
        factors.append(n)
    return factors

print(prime_factors(84))  # [2, 2, 3, 7]

4. Finding Prime Factors by Taking Square Root

5. Fermat Primality Test

C++
// Fermat Primality Test — Probabilistic
#include <iostream>
#include <cstdlib>
using namespace std;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1)
            result = (result * base) % mod;
        exp /= 2;
        base = (base * base) % mod;
    }
    return result;
}

bool fermatTest(int n, int k) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    for (int i = 0; i < k; i++) {
        int a = 2 + rand() % (n - 3);
        if (power(a, n - 1, n) != 1)
            return false;
    }
    return true;
}

Python
# Fermat Primality Test — Probabilistic
import random

def fermat_test(n, k=10):
    if n <= 1: return False
    if n <= 3: return True
    for _ in range(k):
        a = random.randint(2, n - 2)
        if pow(a, n - 1, n) != 1:
            return False
    return True

print(fermat_test(7))    # True
print(fermat_test(561))  # True! (FALSE POSITIVE — Carmichael number)
print(fermat_test(15))   # False

6. Sieve of Eratosthenes ⭐ MOST IMPORTANT

The Sieve of Eratosthenes is the single most important algorithm in this entire unit. It generates ALL prime numbers up to n in O(n log log n) time. If you learn only one thing from this chapter, learn this.

ASCII Visualization: Sieve for n = 30

C++
// Sieve of Eratosthenes — O(n log log n)
#include <iostream>
#include <vector>
using namespace std;

vector<int> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (is_prime[p]) {
            for (int j = p * p; j <= n; j += p)
                is_prime[j] = false;
        }
    }
    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) primes.push_back(i);
    return primes;
}

int main() {
    auto primes = sieve(30);
    cout << "Primes up to 30: ";
    for (int p : primes) cout << p << " ";
    return 0;
}

Python
# Sieve of Eratosthenes — O(n log log n)
def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for j in range(p * p, n + 1, p):
                is_prime[j] = False
        p += 1
    return [i for i in range(2, n + 1) if is_prime[i]]

print(sieve(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

7. Segmented Sieve

When n is very large (say 10⁹), a regular sieve needs a boolean array of 10⁹ entries — about 1 GB of RAM. Most competitive programming judges allow only 256 MB. Solution: segmented sieve.

C++
// Segmented Sieve — find primes in range [L, R]
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<long long> segmentedSieve(long long L, long long R) {
    int limit = (int)sqrt((double)R) + 1;
    vector<bool> mark(limit + 1, true);
    vector<int> small_primes;
    for (int p = 2; p <= limit; p++) {
        if (mark[p]) {
            small_primes.push_back(p);
            for (int j = p * p; j <= limit; j += p)
                mark[j] = false;
        }
    }
    vector<bool> is_prime(R - L + 1, true);
    for (int p : small_primes) {
        long long start = max((long long)p * p, ((L + p - 1) / p) * p);
        for (long long j = start; j <= R; j += p)
            is_prime[j - L] = false;
    }
    if (L == 1) is_prime[0] = false;
    vector<long long> result;
    for (long long i = 0; i <= R - L; i++)
        if (is_prime[i]) result.push_back(L + i);
    return result;
}

Python
# Segmented Sieve — find primes in [L, R]
import math

def segmented_sieve(L, R):
    limit = int(math.sqrt(R)) + 1
    # Step 1: small primes via regular sieve
    mark = [True] * (limit + 1)
    small_primes = []
    for p in range(2, limit + 1):
        if mark[p]:
            small_primes.append(p)
            for j in range(p*p, limit+1, p):
                mark[j] = False
    # Step 2: sieve the range [L, R]
    is_prime = [True] * (R - L + 1)
    for p in small_primes:
        start = max(p * p, ((L + p - 1) // p) * p)
        for j in range(start, R + 1, p):
            is_prime[j - L] = False
    if L == 1: is_prime[0] = False
    return [L + i for i in range(R - L + 1) if is_prime[i]]

print(segmented_sieve(100, 150))
# [101, 103, 107, 109, 113, 127, 131, 137, 139, 149]

8. Sieve of Atkins

The Sieve of Atkins is a modern algorithm that uses quadratic forms and modular arithmetic. It has a theoretical time complexity of O(n / log log n), slightly better than Eratosthenes for very large n.

C++
// Sieve of Atkins — Overview Implementation
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> sieveOfAtkins(int limit) {
    vector<bool> sieve(limit + 1, false);
    if (limit > 2) sieve[2] = true;
    if (limit > 3) sieve[3] = true;
    for (int x = 1; x * x <= limit; x++) {
        for (int y = 1; y * y <= limit; y++) {
            int n = 4 * x * x + y * y;
            if (n <= limit && (n % 12 == 1 || n % 12 == 5))
                sieve[n] = !sieve[n];
            n = 3 * x * x + y * y;
            if (n <= limit && n % 12 == 7)
                sieve[n] = !sieve[n];
            n = 3 * x * x - y * y;
            if (x > y && n <= limit && n % 12 == 11)
                sieve[n] = !sieve[n];
        }
    }
    for (int r = 5; r * r <= limit; r++)
        if (sieve[r])
            for (int i = r * r; i <= limit; i += r * r)
                sieve[i] = false;
    vector<int> primes;
    for (int i = 2; i <= limit; i++)
        if (sieve[i]) primes.push_back(i);
    return primes;
}

9. Mansi and Her Series

Problem: Given N, generate first N terms of a series where: if index i is prime, term[i] = i; otherwise, term[i] = smallest prime factor of i.

C++
// Mansi's Series using Smallest Prime Factor (SPF) sieve
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N = 10;
    vector<int> spf(N + 1);
    for (int i = 0; i <= N; i++) spf[i] = i;
    for (int i = 2; i * i <= N; i++) {
        if (spf[i] == i) {
            for (int j = i * i; j <= N; j += i)
                if (spf[j] == j) spf[j] = i;
        }
    }
    cout << "Mansi's Series: ";
    for (int i = 1; i <= N; i++)
        cout << spf[i] << " ";
    return 0;
}

10. Collections of Pens

Problem: Rohan has N pens. He wants to distribute them equally among groups. Find the total number of ways (= number of divisors of N).

C++
// Count divisors using prime factorization
#include <iostream>
using namespace std;

int countDivisors(int n) {
    int count = 1;
    for (int i = 2; i * i <= n; i++) {
        int exp = 0;
        while (n % i == 0) { exp++; n /= i; }
        count *= (exp + 1);
    }
    if (n > 1) count *= 2;
    return count;
}

int main() {
    int n = 12;
    cout << "N = " << n << ", Ways = " << countDivisors(n) << endl;
    // 12 = 2^2 × 3^1 → (2+1)(1+1) = 6
    return 0;
}

11. Next Prime Palindrome

C++
// Find next number that is both prime AND palindrome
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i+2) == 0) return false;
    return true;
}

bool isPalindrome(int n) {
    string s = to_string(n);
    string r = s;
    reverse(r.begin(), r.end());
    return s == r;
}

int nextPrimePalindrome(int n) {
    int candidate = n + 1;
    while (true) {
        if (isPalindrome(candidate) && isPrime(candidate))
            return candidate;
        candidate++;
    }
}

int main() {
    cout << "Next prime palindrome after 100: " << nextPrimePalindrome(100) << endl;
    cout << "Next prime palindrome after 7: " << nextPrimePalindrome(7) << endl;
    return 0;
}

Learn by Doing — 3-Tier Lab Structure

Problem Set — Practice Questions

Tracing Questions (5)

T1. Trace the Sieve of Eratosthenes for n = 20. Show the array state after each prime's multiples are crossed out.

T2. Trace the O(√n) algorithm for n = 97. List each divisor checked and the final result.

T3. Trace the Fermat test for n = 561 with bases a = 2, 3, 5. Show each computation a^(n-1) mod n.

T4. Trace the prime factorization of n = 360. Show each division step.

T5. Trace the segmented sieve for the range [10, 30] using small primes {2, 3, 5}.

Programming Problems (8)

P1. Count the number of primes up to N. Input: N = 10⁶. Expected output: 78498.

P2. Find the Nth prime number. Input: N = 10001. Expected output: 104743.

P3. Check if a number is a Mersenne prime (of the form 2ᵖ − 1). Test for p = 2, 3, 5, 7, 11, 13.

P4. Find all prime factors of N and print in exponential form. Input: 360 → Output: 2³ × 3² × 5¹.

P5. Generate all twin primes up to N. Twin primes: (3,5), (5,7), (11,13), (17,19), ...

P6. Find the largest prime factor of N. Input: 600851475143. (This is Project Euler Problem 3!)

P7. Count prime palindromes up to N. Input: N = 1000. Expected output: 5 (2, 3, 5, 7, 11).

P8. Sum of all primes up to N using Sieve. Input: N = 2×10⁶. Verify your answer.

Industry Application Problems (3)

I1. RSA Key Generation: Given primes p = 61, q = 53, compute n = p×q, φ(n) = (p-1)(q-1), find e coprime to φ(n), compute d = e⁻¹ mod φ(n). Encrypt and decrypt the message m = 65.

I2. Hash Table Sizing: Write a function that, given N (desired table size), returns the smallest prime ≥ N. This is used in languages like C++ (unordered_map) and Java (HashMap) internally.

I3. Checksum Verification: Implement a prime-based rolling hash for a string. Use a prime modulus (10⁹ + 7) and prime base (31). Verify string integrity after transmission.

Interview Questions (3)

Q1. (Google-style): Given an array of N numbers (each ≤ 10⁶), count how many are prime. Optimize using sieve preprocessing.

Q2. (Amazon-style): Find the k-th prime number efficiently. Can you do better than checking each number?

Q3. (Microsoft-style): Given array A of N integers, count pairs (i, j) where i < j and A[i] + A[j] is prime. Optimize using Goldbach-related observations.

MCQ Assessment Bank — 30 Questions (Bloom's Mapped)

Remember / Identify (Q1–Q5)

Understand / Explain (Q6–Q10)

Apply (Q11–Q15)

Analyze (Q16–Q20)

Evaluate (Q21–Q25)

Create / Design (Q26–Q30)

Short Answer Questions (8)

Long Answer Questions (3)

Lab Programs from Syllabus (5)

C++
#include <iostream>
#include <cmath>
using namespace std;
void primeFactors(int n) {
    while (n % 2 == 0) { cout << 2 << " "; n /= 2; }
    for (int i=3; i*i<=n; i+=2) {
        while (n%i==0) { cout<<i<<" "; n/=i; }
    }
    if (n>1) cout<<n;
    cout<<endl;
}
int main() { primeFactors(84); return 0; }

Python
import random
def power_mod(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1: result = (result * base) % mod
        exp //= 2
        base = (base * base) % mod
    return result

def fermat_test(n, k=10):
    if n < 2: return False
    if n < 4: return True
    for _ in range(k):
        a = random.randint(2, n-2)
        if power_mod(a, n-1, n) != 1: return False
    return True

for n in [7, 15, 561, 997]:
    print(f"{n}: {'Prime' if fermat_test(n) else 'Composite'}")

C++
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n = 50;
    vector<bool> sieve(n+1, true);
    sieve[0] = sieve[1] = false;
    for (int p=2; p*p<=n; p++)
        if (sieve[p])
            for (int j=p*p; j<=n; j+=p)
                sieve[j] = false;
    cout << "Primes up to " << n << ": ";
    for (int i=2; i<=n; i++)
        if (sieve[i]) cout << i << " ";
    return 0;
}

Python
import math
def segmented_sieve(L, R):
    limit = int(math.sqrt(R)) + 1
    mark = [True] * (limit + 1)
    primes = []
    for p in range(2, limit + 1):
        if mark[p]:
            primes.append(p)
            for j in range(p*p, limit+1, p): mark[j] = False
    is_prime = [True] * (R - L + 1)
    for p in primes:
        start = max(p*p, ((L+p-1)//p)*p)
        for j in range(start, R+1, p): is_prime[j-L] = False
    if L <= 1: is_prime[1-L] = False
    return [L+i for i in range(R-L+1) if is_prime[i]]
print(segmented_sieve(100, 150))

Python
import math
def sieve_of_atkins(limit):
    sieve = [False] * (limit + 1)
    for x in range(1, int(math.sqrt(limit)) + 1):
        for y in range(1, int(math.sqrt(limit)) + 1):
            n = 4*x*x + y*y
            if n <= limit and (n%12 == 1 or n%12 == 5):
                sieve[n] = not sieve[n]
            n = 3*x*x + y*y
            if n <= limit and n%12 == 7:
                sieve[n] = not sieve[n]
            n = 3*x*x - y*y
            if x > y and n <= limit and n%12 == 11:
                sieve[n] = not sieve[n]
    for r in range(5, int(math.sqrt(limit)) + 1):
        if sieve[r]:
            for i in range(r*r, limit+1, r*r):
                sieve[i] = False
    return [2,3] + [i for i in range(5, limit+1) if sieve[i]]

print(sieve_of_atkins(100))

Industry Spotlight — A Day in the Life

Earn With It — Freelance & Income Roadmap

Chapter Summary

Earning Checkpoint

✅ Unit 2 complete. Ready for Unit 3!

[QR: Link to EduArtha video tutorial — Primality Testing Deep Dive]