1141 - Number Transformation

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1141

Solution :

#include<bits/stdc++.h>

using namespace std;

bool status[1021];

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

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

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

    prime.push_back(2);

    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;

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

int visited[1020];

int bfs(int s,int d)
{
    int u,p;
    memset(visited,-1,sizeof(visited));

    queue<int>q;

    q.push(s);
    visited[s]=0;

    while(!q.empty())
    {
        u=q.front();
        q.pop();

        for(int i=0; prime[i]<u; i++)
        {
            if(u%prime[i]==0)
            {
                factor.push_back(prime[i]);
            }
        }


        for(int i=0; i<factor.size(); i++)
        {
            p=u+factor[i];

            if(visited[p]==-1 and p<=d)
            {
                visited[p]=visited[u]+1;
                q.push(p);

            }
        }
        factor.clear();
    }
    return visited[d];


}

int main()
{
    int t,a,b,ans;
    sieve();
    scanf("%d",&t);

    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d%d",&a,&b);
        ans=bfs(a,b);
        printf("Case %d: %d\n",ca,ans);
        factor.clear();
    }
}