Prime factorization using sieve of Eratosthenes in C++

By utkarsh bhadauria

An efficient and faster way to find prime factors of a number using sieve of Eratosthenes in C++ programming.

Problem Statement - 

 

Given a number n, we have to deduce its prime factors.

 

Example-

 

Input - 20

 

Output - 2 2 5

 

Algorithmn - 

 

We will try to create a matrix, in which all the numbers in the matrix are marked by their smallest prime factors respectively.

 

We can do this in the following steps -

 

1. We first store the array with all natural numbers, starting with 2 upto n.
2. Starting a loop from 2, we mark all the numbers in the matrix which are divisible by 2 till n with 2.
3. Now, we check the next unmarked element(the numbers which still have not been changed after step 1) in the matrix, and mark the subsequent numbers in the matrix divisible by this number by this number.
4. Now, we can observe that for a given number i, elements less than i*i will already be marked, hence for a element i, we only need to check from i*i to n.

 

After these steps , we will have our matrix ready. Let the matrix name be sp, we use the following code to print our factors.

while(n!=1)
{
    cout << sp[n] << " ";
    n = n/sp[n];
}

 

Code -

 

#include<bits/stdc++.h>
using namespace std;

void primefactors(int n)
{
    int sp[100] = {0};
    for(int i=2;i<=n;i++)
    {
        sp[i] = i;
    }
    for(int i=2;i<=n;i++)
    {
        if(sp[i]==i)
        {
            for(int j=i*i; j<=n;j+=i)
            {
                if(sp[j]==j)
                {
                    sp[j] = i;
                }
            }
        }
    }
    while(n!=1)
    {
        cout << sp[n] << " ";
        n = n/sp[n];
    }
}

int main()
{
    int n;
    cin>>n;
    primefactors(n);
    return 0;
}