Unit 2: Primality Testing

I. Orientation — Testing Whether an Integer Is Prime

Primality testing determines whether an integer greater than 1 has exactly two positive divisors: 1 and itself. It is fundamental in factorization, cryptography, hashing, number-theoretic sequences, and many competitive-programming problems.

A. Introduction to Primality Testing

Primality testing is the process of classifying an integer as prime or composite using divisibility properties.

• Prime definition: An integer (n>1) is prime if its only positive divisors are (1) and (n); examples are (2,3,5,7,11).
• Composite definition: An integer (n>1) is composite if it has a divisor other than (1) and (n); (15) is composite because (15=3\times5).
• Special values: (0) and (1) are neither prime nor composite. The number (2) is the only even prime.
• Central principle: If (n=ab) and both factors were greater than (\sqrt n), then (ab>n). Therefore, every composite (n) has at least one factor at most (\sqrt n).
• Algorithm choice: Trial division is suitable for one moderate number; sieves are better for many queries over a bounded range; probabilistic tests are useful for very large values.

II. O(sqrt(n)) Algorithm for Primality Testing — Deterministic Trial Division

The (O(\sqrt n)) algorithm tests whether any integer from (2) through (\lfloor\sqrt n\rfloor) divides (n).

A. O(sqrt(n)) Algorithm for Primality Testing

The algorithm is correct because a composite number must have a factor no greater than its square root.

• Early conditions: Return false for (n<2); return true for (n=2); reject every even (n>2).
• Loop range: Test odd divisors (d=3,5,7,\ldots) while (d^2\le n). The condition (d^2\le n) avoids floating-point square-root errors.
• Decision rule: If (n\bmod d=0), then (n) is composite; if no divisor is found, (n) is prime.
• Complexity: Testing every integer takes (O(\sqrt n)) time and (O(1)) extra space. Skipping even divisors nearly halves the practical work.

isPrime(n):
    if n < 2:
        return false
    if n == 2:
        return true
    if n % 2 == 0:
        return false

    d = 3
    while d * d <= n:
        if n % d == 0:
            return false
        d += 2
    return true

Here, (n) is the tested integer and (d) is a candidate divisor. Use a wide integer type for d * d when (n) may approach the type limit.

III. Factorization of a Number — Decomposing Into Prime Factors

Factorization expresses an integer as a product of primes. By the Fundamental Theorem of Arithmetic, every integer (n>1) has a unique prime factorization apart from ordering.

A. Factorization of a number

Prime factorization repeatedly removes discovered divisors and records their multiplicities.

• Representation: (360=2^3\times3^2\times5), so the factor pairs are ((2,3),(3,2),(5,1)).
• Repeated division: For each candidate divisor (p), divide while (n\bmod p=0), incrementing the exponent.
• Remaining factor: After testing through (p^2\le n), any remaining (n>1) is itself prime and must be recorded.
• Complexity: Trial factorization takes (O(\sqrt n)) divisions in the worst case and uses (O(1)) auxiliary space.
• Uses: The factors support divisor counting, Euler’s totient function, greatest common divisors, and checking whether a number is a product of selected primes.

IV. Finding Prime Factors by Taking the Square Root — Efficient Factor Search

Taking the square root provides the stopping boundary for trial factorization and prevents unnecessary searches beyond the smallest possible factor.

A. Finding prime factors by taking the square root

A factorization routine tests candidates only while (p^2\le n), updating (n) whenever a factor is removed.

• Why the bound changes: For (n=180), removing (2^2) changes the working value to (45); subsequent candidates need only be tested while (p^2\le45).
• Prime candidates: Testing (2) separately and then odd (p) values avoids all even composite candidates.
• Worked example:
  (84) is divided by (2) twice, leaving (21); (3) divides (21) once, leaving (7). Since (7> \sqrt7), record (7). Thus (84=2^2\times3\times7).
• Important distinction: The original input and the reduced working value must be handled carefully; the final residual factor is not lost.
• Practical limit: This method is effective for individual values but becomes slow when factoring thousands of large numbers.

factor(n):
    factors = empty list
    while n % 2 == 0:
        add 2 to factors
        n /= 2

    p = 3
    while p * p <= n:
        while n % p == 0:
            add p to factors
            n /= p
        p += 2

    if n > 1:
        add n to factors
    return factors

V. Binary Exponentiation — Fast Powers and Modular Powers

Binary exponentiation computes (a^b) in (O(\log b)) multiplications by using the binary representation of the exponent.

A. Binary Exponentiation

The method repeatedly squares the base and processes one exponent bit at a time.

• Power identity: If (b) is even, (a^b=(a^{b/2})^2); if (b) is odd, (a^b=a\cdot a^{b-1}).
• Binary interpretation: For (b=13=(1101)_2), (a^{13}=a^8a^4a^1), requiring only selected powers.
• Modular form: To compute (a^b\bmod m), reduce both result and base after every multiplication.
• Overflow concern: In fixed-width languages, multiplication may overflow before the modulo operation; use a sufficiently wide type or safe modular multiplication.

powerMod(a, b, m):
    result = 1 % m
    a = a % m
    while b > 0:
        if b is odd:
            result = (result * a) % m
        a = (a * a) % m
        b = b // 2
    return result

Here, (a) is the base, (b\ge0) is the exponent, and (m) is the positive modulus. This operation is essential for Fermat-based primality tests.

VI. Fermat Method — A Fast Probabilistic Test

Fermat’s little theorem supplies a necessary condition for primality, but not a sufficient one for all integers.

A. Fermat method

If (p) is prime and (1\le a<p), then (a^{p-1}\equiv1\pmod p). A candidate (n) is tested by choosing bases (a) and computing (a^{n-1}\bmod n).

• Test result: If (\gcd(a,n)=1) and (a^{n-1}\not\equiv1\pmod n), then (n) is definitely composite.
• Probable prime: If the congruence holds for several bases, (n) is called a probable prime, not proven prime.
• Carmichael numbers: Composite values such as (561) can satisfy the Fermat congruence for every base coprime to them; these are pseudoprimes to the Fermat test.
• Complexity: Each base requires (O(\log n)) modular multiplications using binary exponentiation.
• Improvement: Miller–Rabin is generally preferred because it detects many composites that pass Fermat’s test.

fermatTest(n, bases):
    if n < 2:
        return false
    for a in bases:
        if a >= n:
            continue
        if gcd(a, n) != 1:
            return false
        if powerMod(a, n - 1, n) != 1:
            return false
    return true

VII. Sieve of Eratosthenes — All Primes Up to a Limit

The Sieve of Eratosthenes finds every prime not exceeding a chosen limit (N) by marking composite multiples.

A. Sieve of Eratosthenes

The sieve starts with all values marked potentially prime and eliminates multiples of each confirmed prime.

• Initialization: Create isPrime[0..N]; set indices (0) and (1) to false because they are not prime.
• Marking rule: For a prime (p), mark (p^2,p^2+p,p^2+2p,\ldots) as composite. Smaller multiples have already been marked by smaller factors.
• Stopping point: Process only (p\le\sqrt N), because every composite (\le N) has a factor within that range.
• Complexity: Time is (O(N\log\log N)), and memory is (O(N)).
• Example: For (N=20), marking multiples of (2,3), and then (5) leaves (2,3,5,7,11,13,17,19).

sieve(N):
    prime[0..N] = true
    prime[0] = prime[1] = false
    for p = 2 while p * p <= N:
        if prime[p]:
            for multiple = p * p; multiple <= N; multiple += p:
                prime[multiple] = false
    return prime

VIII. Segmented Sieve — Primes in a Large Interval

A segmented sieve finds primes in ([L,R]) without allocating an array for every number up to (R).

A. Segmented Sieve

The method first generates primes up to (\sqrt R), then uses them to mark composites inside the requested interval.

• Base primes: Run the ordinary sieve through (\lfloor\sqrt R\rfloor).
• First multiple: For each base prime (p), begin at
  [
  \max(p^2,\lceil L/p\rceil p).
  ]
  This avoids marking (p) itself when (p\in[L,R]).
• Interval storage: Use segment[0..R-L]; number (x) corresponds to index (x-L).
• Complexity: Memory is (O(R-L+1)); the work is approximately (O(\sqrt R\log\log R+(R-L+1)\log\log R)).
• Boundary case: If (L=1), explicitly mark (1) composite.

IX. Mansi and Her Series — Applying Prime Generation to a Sequence

“Mansi and her series” represents a sequence-based primality task in which efficient generation and repeated prime access matter more than testing each term independently.

A. Mansi and her series

The standard approach is to identify the sequence’s required values, determine the largest queried term or value, and precompute prime information once.

• Precomputation: Build a sieve up to the maximum needed bound (N), giving constant-time primality lookup prime[x].
• Repeated queries: For (q) terms, sieve once in (O(N\log\log N)) and answer each membership query in (O(1)), rather than spending (O(q\sqrt N)) on trial division.
• Sequence indexing: Distinguish carefully between the term index (i) and its numeric value (a_i); test prime[a_i] only when the series definition requires primality.
• Large values: If (a_i) exceeds the sieve limit, use trial division for moderate values or a probabilistic test with modular exponentiation.
• Correctness condition: The chosen bound must cover every value that can occur; an undersized sieve produces incomplete or invalid results.

X. Collections of Pens — Counting Through Prime Factorization

“Collections of Pens” is naturally handled by translating the collection condition into divisibility or factor-count information, where prime factorization exposes the required structure.

A. Collections of Pens

When a problem asks how many equal groups, arrangements, or collections can be formed, the greatest common divisor and prime exponents often provide the decisive computation.

• Common grouping: For quantities (a_1,a_2,\ldots,a_k), the largest equal grouping is (\gcd(a_1,a_2,\ldots,a_k)).
• Factor interpretation: If (n=\prod p_i^{e_i}), each exponent (e_i) describes how many times prime (p_i) can be distributed multiplicatively.
• Divisor count: The number of positive divisors is
  [
  \tau(n)=\prod_i(e_i+1).
  ]
  For (360=2^3\cdot3^2\cdot5), (\tau(360)=4\cdot3\cdot2=24).
• Algorithm selection: Factor one moderate number with square-root trial division; factor many values with a sieve of smallest prime factors.
• Input discipline: Check whether the requested quantity is a number of divisors, a greatest common divisor, or a number of valid collections; these are different outputs despite using related factor data.

XI. Next Prime Palindrome — Combining Palindromes and Primality

The next prime palindrome after (n) is the smallest integer (x>n) that reads identically forward and backward and is prime.

A. Next prime palindrome

A direct solution generates candidate palindromes in increasing order and applies a primality test to each candidate.

• Palindrome construction: Mirror the left half of a number to form the right half. For example, mirroring 123 gives 12321.
• Increasing order: Generate the next palindrome rather than checking every integer, reducing the candidate set substantially.
• Prime filtering: Apply the (O(\sqrt x)) test for moderate bounds; use a stronger test when candidates are large.
• Digit observation: Every even-length palindrome is divisible by (11), except (11) itself. Therefore, for searches beyond (11), prime-palindrome candidates are generally odd-length.
• Example: After (130), the palindromes begin (131,141,151,\ldots); (131) is prime, so it is the next prime palindrome.
• Termination: Continue until a candidate passes both tests: isPalindrome(candidate) and isPrime(candidate).

nextPrimePalindrome(n):
    x = n + 1
    while true:
        if isPalindrome(x) and isPrime(x):
            return x
        x += 1

For large ranges, replace sequential checking with half-string palindrome generation. The key design principle is to combine structural filtering first, through palindrome construction, with arithmetic filtering second, through primality testing.