583 - Prime Factors

Problem Link :https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=524

Solution Idea : Prime factorization.

Solution :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool status[100000];

vector<ll int>prime;
vector<ll int>factor;

void sieve()
{
    ll int n=sqrt(2147483649);
    ll int sq=sqrt(n);

    prime.push_back(2);

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

    for(int i=3; i<=sq; i=i+2)
    {
        if(status[i]==0)
        {
            for(int j=i*i; j<=n; j=j+i)
            {
                status[j]=1;
            }
        }
    }
    status[1]=1;
    status[0]=1;

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

void nod(ll int n,ll int sign)
{
    if(sign==1) n=-1*n;

    ll int sq=sqrt(n);


    for(int i=0; i<prime.size() && prime[i]<=sq; i++)
    {

        while(n%prime[i]==0)
        {
            n=n/prime[i];
            factor.push_back(prime[i]);
        }
        sq=sqrt(n);


    }
    if(n!=1)
    {
        factor.push_back(n);
    }

}

int main()
{
    ll int n,s,p;
    sieve();

    while(scanf("%lld",&n) and n)
    {
        s=0;
        if(n<0) s=1;

        nod(n,s);

        p=factor.size();
        printf("%lld = ",n);
        if(s==1) printf("-1 x ");
        printf("%lld",factor[0]);

        for(int i=1; i<p; i++)
        {
            printf(" x %lld",factor[i]);
        }
        printf("\n");
        factor.clear();
    }

}