Sieve of Eratosthenes [smallest prime factor spf] IMP for number theory Question

Revision en2, by Patel_Utkarsh, 2025-03-18 16:39:09

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. Check numbers are co-prime
co-prime: two number GCD is 1
  
int a,b;
cin>>a>>b;
if(spf[a]!=spf[b])
cout<<"Given numbers are co-prime";


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
Tags number theory, sieve of eratosthenes, factorisation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Patel_Utkarsh 2025-03-18 21:09:55 1374 Tiny change: 'is sorted \nvector <' -> 'is sorted <br>\nvector <'
en3 English Patel_Utkarsh 2025-03-18 20:17:25 284
en2 English Patel_Utkarsh 2025-03-18 16:39:09 1883 Tiny change: 'o 100,000 \nconst int ' -> 'o 100,000 \n- const int ' (published)
en1 English Patel_Utkarsh 2025-03-18 15:05:57 1610 Initial revision (saved to drafts)