Competitive Coding
Unit 2: Primality Testing
From naive checks to blazing-fast sieves — master every primality testing algorithm, crack competitive coding problems, and understand the cryptography that secures India's digital payments.
⏱️ 6 hrs theory + 4 hrs practice | 💰 Earning Potential: ₹5,000–₹25,000/month | 📝 30 MCQs (Bloom's Mapped)
💼 Jobs this unlocks: Cryptography Engineer (₹8–15 LPA) | Security Developer (₹6–12 LPA) | Competitive Programmer
Opening Hook — The Invisible Math Guarding Your Money
🔐 Every UPI Payment You Make is Secured by Prime Numbers
Open PhonePe or Google Pay right now. Send ₹1 to a friend. In that fraction of a second, your phone performed RSA encryption — a cryptographic algorithm that relies entirely on the difficulty of factoring the product of two very large prime numbers (each 300+ digits long).
India's UPI processed 13.89 billion transactions worth ₹20.64 lakh crore in May 2024 alone. Every single one of those transactions was secured by primality testing. The NPCI (National Payments Corporation of India) uses TLS certificates backed by RSA-2048, which depends on 617-digit prime numbers. If someone could efficiently test and factor these primes, they could intercept every payment on PhonePe, Google Pay, Paytm, and BHIM.
What if YOU understood how this works? What if you could implement the same algorithms that protect billions of rupees? That's exactly what this chapter teaches you — from the simplest O(n) check to the blazing-fast Sieve of Eratosthenes used in competitive programming.
Learning Outcomes — Bloom's Taxonomy Mapped
| Bloom's Level | Learning Outcome |
|---|---|
| 🔵 Remember | Define prime numbers and list their fundamental properties (infinitude, distribution, fundamental theorem of arithmetic) |
| 🔵 Remember | State Fermat's Little Theorem and recall the first 25 prime numbers |
| 🟢 Understand | Explain why checking divisibility only up to √n is sufficient for primality testing, with mathematical proof |
| 🟢 Understand | Describe the Sieve of Eratosthenes algorithm step-by-step and trace it for any given n |
| 🟡 Apply | Implement the O(√n) primality test in both C++ and Python with edge-case handling |
| 🟡 Apply | Code the Sieve of Eratosthenes to generate all primes up to N = 10⁷ |
| 🟠 Analyze | Compare time complexities of naive O(n), O(√n), Fermat, and Sieve methods for different input ranges |
| 🟠 Analyze | Analyze why Carmichael numbers are problematic for the Fermat primality test and identify examples |
| 🔴 Evaluate | Assess when to use deterministic vs probabilistic primality tests based on problem constraints |
| 🔴 Evaluate | Evaluate Sieve of Eratosthenes vs Segmented Sieve trade-offs for different memory and range requirements |
| 🟣 Create | Design a comprehensive prime-testing library that combines multiple algorithms with automatic method selection |
| 🟣 Create | Build a segmented sieve for arbitrary range [L, R] queries where R can be up to 10⁹ |