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↵
↵
↵
<br>↵
↵
**C++ code of sieve for spf** <br>↵
<pre style="background: #f4f4f4; padding: 10px; border: 1px solid #ddd;">↵
<code>↵
↵
const int MAX_VAL = 1e5 + 5; ↵
int spf[MAX_VAL]; ↵
↵
void sieve() { <br>↵
for (int i = 1; i <= 100000; ++i) { ↵
spf[i] = i; ↵
}↵
↵
for (int i = 2; i * i <= 100000; ++i) {↵
if (spf[i] == i) { ↵
for (int j = i * i; j <= 100000; j += i) {↵
if (spf[j] == j) { ↵
spf[j] = i;↵
}↵
}↵
}↵
}↵
}↵
↵
int main() {↵
sieve();↵
return 0;↵
}↵
</code>↵
</pre>↵
↵
### Use of spf ↵
↵
**1. Check number is prime**↵
<pre style="background: #f4f4f4; padding: 10px; border: 1px solid #ddd;">↵
<code>↵
<br>↵
int a;<br>↵
cin>>a;<br>↵
if(spf[a]==a)<br>↵
cout<<"Given number is prime";<br>↵
</code>↵
</pre>↵
<br>↵
<br>↵
**2. Check number is semi-prime**<br>↵
semi-prime: Product of two prime numbers (may be both are equal) Example: 25=5*5, 4=2*2, 77=7*11↵
<pre style="background: #f4f4f4; padding: 10px; border: 1px solid #ddd;">↵
<code>↵
<br>↵
int a;<br>↵
cin>>a;<br>↵
int x=spf[a];<br>↵
int y=a/x;<br>↵
if(spf[x]==x && spf[y]==y)<br>↵
cout<<"Given number is semi-prime";<br>↵
</code>↵
</pre>↵
<br>↵
<br>↵
**3. Check numbers are co-prime**<br>↵
co-prime: two number GCD is 1 ↵
<pre style="background: #f4f4f4; padding: 10px; border: 1px solid #ddd;">↵
<code>↵
<br>↵
int a,b;<br>↵
cin>>a>>b;<br>↵
if(spf[a]!=spf[b])<br>↵
cout<<"Given numbers are co-prime";<br>↵
</code>↵
</pre>↵
<br>↵
<br>↵
**4. Finding the Prime Factorization of a Number**<br>↵
<pre style="background: #f4f4f4; padding: 10px; border: 1px solid #ddd;">↵
<code>↵
<br>↵
int n;<br>↵
cin>>n;<br>↵
int x=n;<br>↵
while(x!=1){<br>↵
cout<<spf[x]<<" ";<br>↵
x=x/spf[x];<br>↵
}<br>↵
</code>↵
</pre>↵
<pre style="background: #f4f4f4; padding: 10px; border: 1px solid #ddd;">↵
<code>↵
<br>↵
Input: 60<br>↵
Output: 2 2 3 5<br>↵
</code>↵
</pre>↵
↵
↵
↵
#### 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↵
↵
↵
↵
**C++ code of sieve for spf** <br>↵
<pre style="background: #f4f4f4; padding: 10px; border: 1px solid #ddd;">↵
<code>↵
↵
const int MAX_VAL = 1e5 + 5; ↵
int spf[MAX_VAL]; ↵
↵
void sieve() { <br>↵
for (int i = 1; i <= 100000; ++i) { ↵
spf[i] = i; ↵
}↵
↵
for (int i = 2; i * i <= 100000; ++i) {↵
if (spf[i] == i) { ↵
for (int j = i * i; j <= 100000; j += i) {↵
if (spf[j] == j) { ↵
spf[j] = i;↵
}↵
}↵
}↵
}↵
}↵
↵
int main() {↵
sieve();↵
return 0;↵
}↵
</code>↵
</pre>↵
↵
### Use of spf ↵
↵
**1. Check number is prime**↵
<pre style="background: #f4f4f4; padding: 10px; border: 1px solid #ddd;">↵
<code>↵
<br>↵
int a;<br>↵
cin>>a;<br>↵
if(spf[a]==a)<br>↵
cout<<"Given number is prime";<br>↵
</code>↵
</pre>↵
<br>↵
<br>↵
**2. Check number is semi-prime**<br>↵
semi-prime: Product of two prime numbers (may be both are equal) Example: 25=5*5, 4=2*2, 77=7*11↵
<pre style="background: #f4f4f4; padding: 10px; border: 1px solid #ddd;">↵
<code>↵
<br>↵
int a;<br>↵
cin>>a;<br>↵
int x=spf[a];<br>↵
int y=a/x;<br>↵
if(spf[x]==x && spf[y]==y)<br>↵
cout<<"Given number is semi-prime";<br>↵
</code>↵
</pre>↵
<br>↵
<br>↵
**3. Check numbers are co-prime**<br>↵
co-prime: two number GCD is 1 ↵
<pre style="background: #f4f4f4; padding: 10px; border: 1px solid #ddd;">↵
<code>↵
<br>↵
int a,b;<br>↵
cin>>a>>b;<br>↵
if(spf[a]!=spf[b])<br>↵
cout<<"Given numbers are co-prime";<br>↵
</code>↵
</pre>↵
<br>↵
<br>↵
**4. Finding the Prime Factorization of a Number**<br>↵
<pre style="background: #f4f4f4; padding: 10px; border: 1px solid #ddd;">↵
<code>↵
<br>↵
int n;<br>↵
cin>>n;<br>↵
int x=n;<br>↵
while(x!=1){<br>↵
cout<<spf[x]<<" ";<br>↵
x=x/spf[x];<br>↵
}<br>↵
</code>↵
</pre>↵
<pre style="background: #f4f4f4; padding: 10px; border: 1px solid #ddd;">↵
<code>↵
<br>↵
Input: 60<br>↵
Output: 2 2 3 5<br>↵
</code>↵
</pre>↵
↵
↵
