Prime Factorization of Factorial Source code

Tutorial Link : http://blog.forthright48.com/2015/08/prime-factorization-of-factorial.html

Source Code :

#include<bits/stdc++.h>

using namespace std;

bool status[1100001];

vector<int>prime;

void sieve()
{
    int n=1000001;
    int sq=sqrt(n);

    for(int i=4;i<=n;i=i+2) status[i]=true;

    for(int i=3;i<=sq;i=i+2)
    {
        if(status[i]==false)
        {

            for(int j=i*i;j<=n;j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    prime.push_back(2);

    for(int i=3;i<=n;i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}

void fact ( int n ) {
    for ( int i = 0; i < prime.size() and prime[i]<= n; i++ ) {
        int x = n;
        int freq = 0;

        while ( x / prime[i] ) {
            freq += x / prime[i];
            x = x / prime[i];
        }

        printf ( "%d^%d ", prime[i], freq );
    }
}
int main()
{
    sieve();

    int n;
    cin>>n;
    fact(n);

}