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.

C++ code of sieve for spf

 
const int MAX_VAL = 1e5 + 5; int spf[MAX_VAL]; 
void sieve() { 
  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; }  

Use of spf

1. Check number is prime

  
 int a;
 cin>>a;
 if(spf[a]==a)
 cout<<"Given number is prime";
  

  
 int a;
 cin>>a;
 int x=spf[a];
 int y=a/x;
 if(spf[x]==x && spf[y]==y)
 cout<<"Given number is semi-prime";
  

  
 int n;
 cin>>n;
 int x=n;
 while(x!=1){
 cout<<spf[x]<<" ";
 x=x/spf[x];
 }
  

  
 Input: 60
 Output: 2 2 3 5
  

  
 // Function to compute the prime factorization of a number n 
 // The result is returned as a sorted vector of prime factors. 
 vector < int > factorization(int n){
 vector < int > ans;
 int x=n;
 while(x!=1){
 ans.push_back(spf[x]); x=x/spf[x];
 }
 return ans;
 }
 
 
 // Function to check if two sorted vectors have no common elements 
 // It returns true if the vectors have no common elements, otherwise false 
 bool have_no_common_element(vector < int > &a,vector < int > &b){
 int p1=0,p2=0;
 while(p1<a.size() && p2<b.size()){
 if(a[p1]==b[p2])
 return false;
 else if(a[p1]<b[p2])
 p1++;
 else
 p2++; }
 return true;
 }
 
 
 int a,b;
 cin>>a>>b;
 vector < int >factor_of_a=factorization(a);
 vector < int >factor_of_b=factorization(b);
 if(have_no_common_element(factor_of_a,factor_of_b))
 cout<<"Given numbers are co-prime";
  

Also, Directly use in built __gcd() function

int a,b;

cin>>a>>b;

if(__gcd(a,b)==1)

cout<<"Given numbers are co-prime";