The Lewis Sieve Factorization

Factorization by Default: A Step-by-Step Guide to the Lewis Sieve

The classical Sieve of Eratosthenes is celebrated for its simplicity in isolating prime numbers. However, while it efficiently eliminates composites, it stops short of giving any insight into the factors that caused that elimination. In contrast, the Lewis Sieve extends this idea by “propagating” the influence of each prime through a target range. As a result, it not only filters out composites but also records the factorization information by default. In other words, if you want to factor a number, you can use the Lewis Sieve—without resorting to brute force.

In this post, we’ll walk through the process, formalize the algorithm, and provide proofs of correctness.

---

1. Preliminaries: The Classical Sieve of Eratosthenes

1.1. The Basic Algorithm

Given a number $n$, the Sieve of Eratosthenes works as follows:

1. Initialization:
   Create a list of numbers $A = \{2, 3, 4, \dots, n\}$ and mark each as "potential prime."

2. Sieving Process:
   For each number $p$ from $2$ to $\lfloor \sqrt{n} \rfloor$:

   • If $p$ is still marked as prime, then $p$ is prime.
   • Mark every multiple of $p$ (starting from $p^2$) as composite.

3. Output:
   The remaining unmarked numbers are the primes up to $n$.

1.2. Correctness Proof (Briefly)

• Soundness:
  Assume an unmarked number $q$ is composite. Then $q = a \times b$ with $2 \le a \le \sqrt{q}$. Since $a \le \sqrt{n}$, $a$ would have been processed and would mark $q$ as composite—a contradiction.

• Completeness:
  Every composite number $q$ has a prime factor $p \le \sqrt{q} \le \sqrt{n}$ that will eventually mark it. Thus, every composite is removed.

The sieve gives us a flat list of primes—but nothing more.

---

2. The Lewis Sieve: Extending to Factorization

2.1. The Key Idea

The Lewis Sieve builds on the classical sieve by adding a propagation (or reinforcement) step. As it eliminates composites, it “records” which prime was responsible. Thus, if you target a specific composite number $N$, you can trace its factorization by observing which prime(s) eliminated it.

2.2. The Process Step by Step

Let’s assume you wish to factor a composite number $N$. The process is as follows:

Step 1. Precompute Base Primes

1. Compute all primes up to $\lfloor \sqrt{N} \rfloor$.
   This is done using the classical Sieve of Eratosthenes.
   Let $$P = \{p_1, p_2, \dots, p_k\}$$ be the list of these base primes.

Step 2. Segmented Sieving and Propagation

2. Choose a segment (an interval) that contains $N$.
   For example, if $N$ lies in $[S, E]$ (with $S \le N \le E$), initialize an array of Boolean flags for each number in the segment—all set to True (meaning “potential prime”).

3. For each prime $p$ in $P$:

   • Find the first multiple in the segment:
     Compute $$m_p = \max(p^2, \lceil S/p \rceil \times p)$$ which is the smallest multiple of $p$ within $[S, E]$.
   • Propagate $p$'s influence:
     For every multiple $m_p, m_p + p, m_p + 2p, \dots$ in the segment, mark it as composite.
     Record: If the composite number $N$ is reached during this process, note that $p$ is a divisor of $N$.

Step 3. Factorization via Recorded Data

4. Once the sieve has been executed, there are two possibilities for $N$:
   • Case 1: $N$ remains unmarked.
     Then $N$ is prime.
   • Case 2: $N$ is marked composite.
     The first base prime $p$ that marked $N$ (typically the smallest such prime) is a factor of $N$.
     Set $q = N / p$.
     You can then recursively factor $q$ using the same process or a classical method.

---

3. Formalization of the Factorization Process

3.1. Algorithmic Pseudocode

def lewis_factorization(N):
    # Base case: if N is prime, return [N]
    if is_prime(N):
        return [N]
    
    # Step 1: Compute base primes up to sqrt(N)
    limit = int(N**0.5) + 1
    base_primes = sieve_of_eratosthenes(limit)
    
    # Step 2: Find the smallest factor of N via propagation
    factor = None
    for p in base_primes:
        if N % p == 0:
            factor = p
            break
    
    # At this point, factor is the smallest prime factor of N.
    # Factorize the quotient recursively.
    other_factor = N // factor
    return [factor] + lewis_factorization(other_factor)

# Helper: Classical Sieve of Eratosthenes to compute primes up to n.
def sieve_of_eratosthenes(n):
    sieve = [True] * (n+1)
    sieve[0:2] = [False, False]
    for i in range(2, int(n**0.5)+1):
        if sieve[i]:
            for j in range(i*i, n+1, i):
                sieve[j] = False
    return [i for i, is_prime in enumerate(sieve) if is_prime]

# Helper: A simple primality test.
def is_prime(n):
    if n < 2: return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

3.2. Formal Proof of Correctness

Theorem:
Let $N$ be a composite number and $P$ be the set of primes up to $\lfloor \sqrt{N} \rfloor$. Then the first prime $p \in P$ such that $p \mid N$ is the smallest prime factor of $N$.

Proof Sketch:

1. Existence of a Factor:
   By the Fundamental Theorem of Arithmetic, any composite $N$ has at least one prime factor $p$ such that $p \le \sqrt{N}$. Hence, $P$ is guaranteed to contain at least one divisor of $N$.

2. Determinism of the Lewis Sieve:
   The process checks each prime in $P$ in increasing order. The first $p$ encountered that satisfies $N \mod p = 0$ is necessarily the smallest prime factor of $N$.

3. Propagation:
   In the Lewis Sieve, when sieving a segment containing $N$, the same $p$ would be used to mark $N$ as composite. The fact that $N$ is eliminated due to $p$ inherently records that $p$ divides $N$.

4. Recursion and Completeness:
   After finding the smallest factor $p$, the algorithm recursively factors the quotient $N/p$ using the same method. This process terminates because $N$ decreases at each step, eventually reaching prime numbers.

Thus, the Lewis Sieve not only isolates primes but, by the very design of its elimination and propagation steps, provides a complete factorization of $N$.

---

4. Conclusion

The Lewis Sieve represents a conceptual leap from the Sieve of Eratosthenes. While Eratosthenes simply filters out composites to leave a list of primes, the Lewis Sieve propagates the elimination process—thereby automatically recording which prime factors are responsible for eliminating a composite number. This built-in factorization is not only elegant but also provides a powerful alternative to brute force factorization.

Whether you’re generating primes, analyzing number structures, or factoring a composite number, the Lewis Sieve offers a unified, deterministic approach that factors by default.