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";
  

2. Check number is semi-prime
semi-prime: Product of two prime numbers (may be both are equal) Example: 25=5*5, 4=2*2, 77=7*11

  
 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";
  

3. Given number have exactly 3 divisors?
Number have exactly 3 divisors only in case number is square of prime number
Example: 49 (divisors: 1 7 49),169 (divisors: 1 13 169)

  
 int a;
 cin>>a;
 int x=spf[a];
 int y=a/x;
 if(x==y && spf[x]==x && spf[y]==y)
 cout<<"Given number have exactly 3 divisors";
  

But what if Given number big like 1e8 (10^8) OR (10^9)? Then is algorithm is not work?
Answer: In that case First check number is perfect square or not. If number is perfect square then check square root is prime number or not square root(10^8)=10000 and square root(10^10)=100000

  
 int a;
 cin>>a;
 int sq=sqrt(a); 
 if(sq*sq==a && spf[sq]==sq)
 cout<<"Given number have exactly 3 divisors";
  

4. Finding the Prime Factorization of a Number

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

  
 Input: 60
 Output: 2 2 3 5
  

5. Check numbers are co-prime

  
 // 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 this is better way

int a,b;

cin>>a>>b;

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

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