Factor an entire range of numbers using the Lewis Sieve

[mikelewis]

Last edited Mon Feb 17, 2025, 08:50 AM - Edit history (5)

The Lewis Sieve: A Combined Method for Finding Primes and Instantly Factoring Numbers

Overview

The Lewis Sieve is an extension of the classic Sieve of Eratosthenes. Its core idea is simple yet powerful: as you eliminate composite numbers from a specific range, you also “tag” each composite with the smallest prime factor that divides it. This tag then gives you instant access to a factor of the number. Because of the underlying mathematics, there’s no way a prime number will ever be incorrectly tagged.

Why Use the Lewis Sieve?

1. Targeted Processing:
Instead of processing every number from 2 to a huge maximum, you focus on a smaller, manageable interval. This makes the process faster and saves on memory.

2. Built-in Factorization:
While the traditional Sieve of Eratosthenes only tells you which numbers are prime, the Lewis Sieve also gives you the smallest prime factor for every composite number in your chosen range. This means you can factor numbers immediately without doing extra division tests.

3. Guaranteed Accuracy:
The method relies on the Fundamental Theorem of Arithmetic, which tells us that every composite number has at least one prime factor less than or equal to its square root. By generating all primes up to that square root (our “base primes”), the algorithm guarantees that every composite will be correctly tagged by its smallest factor, and no prime will ever be tagged since it is not divisible by any smaller prime.

Step-by-Step Instructions

Step 1: Define Your Target Range

Decide on the interval you want to work with. For instance, suppose you want to factor numbers between 48,000 and 48,500. This is your target range.

Step 2: Generate Your Base Primes

1. Calculate the Limit:
Take the highest number in your range (48,500 in our example) and compute its square root. This value is approximately 220.

2. Run the Classic Sieve:
Use the Sieve of Eratosthenes on the numbers from 2 to 220 to produce all primes up to 220. These primes will be used to test divisibility in your target range. They are known as your “base primes.”

Step 3: Prepare Your Work Area

- List Your Numbers:
Write down or create an array for every number in your target range (48,000 to 48,500).

- Tag Field:
For each number, prepare a “tag” field that is initially empty. This field will later record the smallest prime factor that divides the number (if any).

Step 4: Run the Sieve with Factor Propagation

For each base prime p (starting with 2, then 3, 5, 7, etc.), do the following:

1. Determine the First Multiple:
Calculate the first number in your target range that is divisible by p. This is given by taking the maximum of p^2 and the smallest multiple of p that is at least as big as the start of your range.
- For example, if p = 2 and your range starts at 48,000 (which is even), then 48,000 is the first multiple.

2. Mark and Tag:
Walk through your target range in increments of p (i.e., 48,000, 48,002, 48,004, … for p = 2). For each number n that is a multiple of p:
- Mark n as Composite:
This tells you that n is not prime.
- Record the Factor:
If n has not already been tagged with a factor, set its tag to p. This means “p is the smallest prime factor of n.”

3. Proceed to the Next Base Prime:
Repeat the process for every base prime in your list.
- If a composite number is divisible by more than one base prime, it will get tagged by the smallest one—the first one to divide it during this process. Since you process the primes in increasing order, this is guaranteed.

Step 5: Read the Results

After processing all base primes:
- Unmarked Numbers:
Any number in your target range that remains unmarked is prime.
- Tagged Composites:
Each composite number now has a tag that indicates its smallest prime factor. For complete factorization, divide the composite by its tag and, if necessary, apply the method recursively to the quotient.

The Mathematical Guarantee

The key point is that every composite number n has at least one prime factor p with p with p < = √n (this is the Fundamental Theorem of Arithmetic). Since our base primes include all primes up to √E (with E being the maximum of our range), every composite in the range must be divisible by one of these base primes. Thus:

Every composite number will be marked by the first (smallest) base prime that divides it.
A prime number will never be marked because none of the base primes divide it.
This mechanism guarantees that no prime is mistakenly tagged, and every composite gets its correct smallest prime factor as a tag.

In Summary

The Lewis Sieve lets you work on a manageable section of numbers, efficiently identifies the primes, and simultaneously tags every composite with its smallest prime factor. This dual action means you can instantly factor any composite number in the range without extra steps. By relying on solid mathematical principles, it guarantees that the factor information is correct and that primes remain untouched.

This method isn’t just an incremental improvement—it’s a natural evolution of the classical sieve, combining prime detection and factorization into one clean, efficient process.

Happy sieving! Use the Lewis Sieve to uncover both the primes and the factors hidden in your number ranges with confidence.


def lewis_sieve_teaching(target_start, target_end):

"""
The Lewis Sieve processes a target range [target_start, target_end]
and performs two tasks:
1. It identifies which numbers are prime.
2. It finds all prime factors for each composite number using only the sieve process.

The process:
- Compute base primes up to sqrt(target_end) using the classic sieve.
- For each base prime, mark its multiples in the target range.
- Maintain a list of all prime factors for each composite number during the sieve process.
"""

print("n=== The Lewis Sieve: Prime Detection and Factorization ===n" )
print(f"Target Range: {target_start} to {target_end}n " )

# Step 1: Determine the upper limit for base primes (square root of target_end)
limit = int(math.sqrt(target_end)) + 1
print(f"Step 1: Compute base primes up to {limit}n" )
base_primes = sieve_of_eratosthenes(limit)
print("Base Primes Used for Sieving:", base_primes)
print("-" * 50 )

# Step 2: Prepare our work area for the target range
numbers = list(range(target_start, target_end + 1 ) )
composite = {n: False for n in numbers}
factors = { n: [ ] for n in numbers}

print("nStep 2: Processing Base Primes to Identify Factorsn" )
for p in base_primes:

first_multiple = max ( p * p, ( (target_start + p - 1) // p ) * p )
if first_multiple > target_end:

print(f"Skipping prime {p} (first multiple {first_multiple} is outside the range)n" )
continue

print(f"Processing prime {p}: First multiple in range is {first_multiple} " )

for multiple in range(first_multiple, target_end + 1, p) :

if multiple in composite:

composite[multiple] = True

if p not in factors[multiple]:

factors[multiple].append(p)

print(f" Marking {multiple} as composite; current factors: {factors[multiple] } " )

print("nStep 3: Final Resultsn" )
result_table = []
for n in numbers:

if composite[n]:

result_table.append( (n, f"Composite, factors = {factors[n] } " ) )
print(f" {n}: Composite, factors = {factors[n] } " )

else:

result_table.append( (n, "Prime" ) )
print(f" {n}: Prime" )

# Convert to DataFrame for structured display
df_teaching = pd.DataFrame(result_table, columns=["Number", "Status" ] )

# Display results
tools.display_dataframe_to_user(name="Lewis Sieve Teaching Results", dataframe=df_teaching)

return composite, factors

# Run the improved teaching version of Lewis Sieve
composite_teaching, factors_teaching = lewis_sieve_teaching(target_start, target_end)

== The Lewis Sieve: Prime Detection and Factorization ===

Target Range: 48000 to 48050

Step 1: Compute base primes up to 220

Base Primes Used for Sieving: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211]
--------------------------------------------------

Step 2: Processing Base Primes to Identify Factors

Processing prime 2: First multiple in range is 48000
Marking 48000 as composite; current factors: [2]
Marking 48002 as composite; current factors: [2]
Marking 48004 as composite; current factors: [2]
Marking 48006 as composite; current factors: [2]
Marking 48008 as composite; current factors: [2]
Marking 48010 as composite; current factors: [2]
Marking 48012 as composite; current factors: [2]
Marking 48014 as composite; current factors: [2]
Marking 48016 as composite; current factors: [2]
Marking 48018 as composite; current factors: [2]
Marking 48020 as composite; current factors: [2]
Marking 48022 as composite; current factors: [2]
Marking 48024 as composite; current factors: [2]
Marking 48026 as composite; current factors: [2]
Marking 48028 as composite; current factors: [2]
Marking 48030 as composite; current factors: [2]
Marking 48032 as composite; current factors: [2]
Marking 48034 as composite; current factors: [2]
Marking 48036 as composite; current factors: [2]
Marking 48038 as composite; current factors: [2]
Marking 48040 as composite; current factors: [2]
Marking 48042 as composite; current factors: [2]
Marking 48044 as composite; current factors: [2]
Marking 48046 as composite; current factors: [2]
Marking 48048 as composite; current factors: [2]
Marking 48050 as composite; current factors: [2]
Processing prime 3: First multiple in range is 48000
Marking 48000 as composite; current factors: [2, 3]
Marking 48003 as composite; current factors: [3]
Marking 48006 as composite; current factors: [2, 3]
Marking 48009 as composite; current factors: [3]
Marking 48012 as composite; current factors: [2, 3]
Marking 48015 as composite; current factors: [3]
Marking 48018 as composite; current factors: [2, 3]
Marking 48021 as composite; current factors: [3]
Marking 48024 as composite; current factors: [2, 3]
Marking 48027 as composite; current factors: [3]
Marking 48030 as composite; current factors: [2, 3]
Marking 48033 as composite; current factors: [3]
Marking 48036 as composite; current factors: [2, 3]
Marking 48039 as composite; current factors: [3]
Marking 48042 as composite; current factors: [2, 3]
Marking 48045 as composite; current factors: [3]
Marking 48048 as composite; current factors: [2, 3]
Processing prime 5: First multiple in range is 48000
Marking 48000 as composite; current factors: [2, 3, 5]
Marking 48005 as composite; current factors: [5]
Marking 48010 as composite; current factors: [2, 5]
Marking 48015 as composite; current factors: [3, 5]
Marking 48020 as composite; current factors: [2, 5]
Marking 48025 as composite; current factors: [5]
Marking 48030 as composite; current factors: [2, 3, 5]
Marking 48035 as composite; current factors: [5]
Marking 48040 as composite; current factors: [2, 5]
Marking 48045 as composite; current factors: [3, 5]
Marking 48050 as composite; current factors: [2, 5]
Processing prime 7: First multiple in range is 48006
Marking 48006 as composite; current factors: [2, 3, 7]
Marking 48013 as composite; current factors: [7]
Marking 48020 as composite; current factors: [2, 5, 7]
Marking 48027 as composite; current factors: [3, 7]
Marking 48034 as composite; current factors: [2, 7]
Marking 48041 as composite; current factors: [7]
Marking 48048 as composite; current factors: [2, 3, 7]
Processing prime 11: First multiple in range is 48004
Marking 48004 as composite; current factors: [2, 11]
Marking 48015 as composite; current factors: [3, 5, 11]
Marking 48026 as composite; current factors: [2, 11]
Marking 48037 as composite; current factors: [11]
Marking 48048 as composite; current factors: [2, 3, 7, 11]
Processing prime 13: First multiple in range is 48009
Marking 48009 as composite; current factors: [3, 13]
Marking 48022 as composite; current factors: [2, 13]
Marking 48035 as composite; current factors: [5, 13]
Marking 48048 as composite; current factors: [2, 3, 7, 11, 13]
Processing prime 17: First multiple in range is 48008
Marking 48008 as composite; current factors: [2, 17]
Marking 48025 as composite; current factors: [5, 17]
Marking 48042 as composite; current factors: [2, 3, 17]
Processing prime 19: First multiple in range is 48013
Marking 48013 as composite; current factors: [7, 19]
Marking 48032 as composite; current factors: [2, 19]
Processing prime 23: First multiple in range is 48001
Marking 48001 as composite; current factors: [23]
Marking 48024 as composite; current factors: [2, 3, 23]
Marking 48047 as composite; current factors: [23]
Processing prime 29: First multiple in range is 48024
Marking 48024 as composite; current factors: [2, 3, 23, 29]
Processing prime 31: First multiple in range is 48019
Marking 48019 as composite; current factors: [31]
Marking 48050 as composite; current factors: [2, 5, 31]
Processing prime 37: First multiple in range is 48026
Marking 48026 as composite; current factors: [2, 11, 37]
Processing prime 41: First multiple in range is 48011
Marking 48011 as composite; current factors: [41]
Processing prime 43: First multiple in range is 48031
Marking 48031 as composite; current factors: [43]
Processing prime 47: First multiple in range is 48034
Marking 48034 as composite; current factors: [2, 7, 47]
Processing prime 53: First multiple in range is 48018
Marking 48018 as composite; current factors: [2, 3, 53]
Processing prime 59: First multiple in range is 48026
Marking 48026 as composite; current factors: [2, 11, 37, 59]
Processing prime 61: First multiple in range is 48007
Marking 48007 as composite; current factors: [61]
Processing prime 67: First multiple in range is 48039
Marking 48039 as composite; current factors: [3, 67]
Skipping prime 71 (first multiple 48067 is outside the range)

Processing prime 73: First multiple in range is 48034
Marking 48034 as composite; current factors: [2, 7, 47, 73]
Processing prime 79: First multiple in range is 48032
Marking 48032 as composite; current factors: [2, 19, 79]
Skipping prime 83 (first multiple 48057 is outside the range)

Skipping prime 89 (first multiple 48060 is outside the range)

Processing prime 97: First multiple in range is 48015
Marking 48015 as composite; current factors: [3, 5, 11, 97]
Skipping prime 101 (first multiple 48076 is outside the range)

Skipping prime 103 (first multiple 48101 is outside the range)

Processing prime 107: First multiple in range is 48043
Marking 48043 as composite; current factors: [107]
Skipping prime 109 (first multiple 48069 is outside the range)

Processing prime 113: First multiple in range is 48025
Marking 48025 as composite; current factors: [5, 17, 113]
Processing prime 127: First multiple in range is 48006
Marking 48006 as composite; current factors: [2, 3, 7, 127]
Skipping prime 131 (first multiple 48077 is outside the range)

Skipping prime 137 (first multiple 48087 is outside the range)

Skipping prime 139 (first multiple 48094 is outside the range)

Skipping prime 149 (first multiple 48127 is outside the range)

Processing prime 151: First multiple in range is 48018
Marking 48018 as composite; current factors: [2, 3, 53, 151]
Processing prime 157: First multiple in range is 48042
Marking 48042 as composite; current factors: [2, 3, 17, 157]
Skipping prime 163 (first multiple 48085 is outside the range)

Skipping prime 167 (first multiple 48096 is outside the range)

Skipping prime 173 (first multiple 48094 is outside the range)

Skipping prime 179 (first multiple 48151 is outside the range)

Skipping prime 181 (first multiple 48146 is outside the range)

Skipping prime 191 (first multiple 48132 is outside the range)

Skipping prime 193 (first multiple 48057 is outside the range)

Skipping prime 197 (first multiple 48068 is outside the range)

Skipping prime 199 (first multiple 48158 is outside the range)

Skipping prime 211 (first multiple 48108 is outside the range)


Step 3: Final Results

48000: Composite, factors = [2, 3, 5]
48001: Composite, factors = [23]
48002: Composite, factors = [2]
48003: Composite, factors = [3]
48004: Composite, factors = [2, 11]
48005: Composite, factors = [5]
48006: Composite, factors = [2, 3, 7, 127]
48007: Composite, factors = [61]
48008: Composite, factors = [2, 17]
48009: Composite, factors = [3, 13]
48010: Composite, factors = [2, 5]
48011: Composite, factors = [41]
48012: Composite, factors = [2, 3]
48013: Composite, factors = [7, 19]
48014: Composite, factors = [2]
48015: Composite, factors = [3, 5, 11, 97]
48016: Composite, factors = [2]
48017: Prime
48018: Composite, factors = [2, 3, 53, 151]
48019: Composite, factors = [31]
48020: Composite, factors = [2, 5, 7]
48021: Composite, factors = [3]
48022: Composite, factors = [2, 13]
48023: Prime
48024: Composite, factors = [2, 3, 23, 29]
48025: Composite, factors = [5, 17, 113]
48026: Composite, factors = [2, 11, 37, 59]
48027: Composite, factors = [3, 7]
48028: Composite, factors = [2]
48029: Prime
48030: Composite, factors = [2, 3, 5]
48031: Composite, factors = [43]
48032: Composite, factors = [2, 19, 79]
48033: Composite, factors = [3]
48034: Composite, factors = [2, 7, 47, 73]
48035: Composite, factors = [5, 13]
48036: Composite, factors = [2, 3]
48037: Composite, factors = [11]
48038: Composite, factors = [2]
48039: Composite, factors = [3, 67]
48040: Composite, factors = [2, 5]
48041: Composite, factors = [7]
48042: Composite, factors = [2, 3, 17, 157]
48043: Composite, factors = [107]
48044: Composite, factors = [2]
48045: Composite, factors = [3, 5]
48046: Composite, factors = [2]
48047: Composite, factors = [23]
48048: Composite, factors = [2, 3, 7, 11, 13]
48049: Prime
48050: Composite, factors = [2, 5, 31]