The Sieve of Eratosthenes is an efficient algorithm used to find all prime numbers up to a given limit, n. It can also be modified to find the Smallest Prime Factor (SPF) for each number up to n. In this blog, we will understand the concept of Smallest Prime Factor (SPF) and how it is computed using the Sieve of Eratosthenes.

Definition

Prime Number: A prime number is a number greater than 1 that is only divisible by 1 and itself. For example, 7 is a prime number because its only divisors are 1 and 7. Similarly, 13, 17, 23, and so on are prime numbers.

Smallest Prime Factor (SPF): The Smallest Prime Factor (SPF) of a number n is the smallest prime number that divides n. If n is a prime number, its smallest prime factor is the number itself.

Example: For n = 35, the prime factorization is 35 = 5 * 7. Hence, the smallest prime factor (SPF) of 35 is 5, which is the smallest prime factor in the factorization.

Sieve of Eratosthenes for Computing SPF:

The Sieve of Eratosthenes can be used to precompute the Smallest Prime Factor (SPF) for all numbers from 1 to n. Here's the basic idea behind the algorithm:

Initially, assume that each number is its own smallest prime factor. For each prime number p, iterate through all multiples of p and set their smallest prime factor to p. This method allows us to compute the SPF for all numbers up to 100,000 efficiently in O(n log log n) time complexity.

Code to Compute SPF for Numbers from 1 to 100,000