11730 – Number Transformation

Problem Link

Same Problem : LightOJ

#Solution

#include<bits/stdc++.h>
using namespace std;
#define N 1010
int prime[N];
void sieve(){
bool notprime[N]={true,true};
for(int i=2;i<=50;i++)
for(int j=2*i;j<=N;j+=i)
notprime[j]=true;

int c=0;

for(int i=2;i<N;i++)
if(!notprime[i]) prime[c++]=i;
}
int bfs(int s,int t)
{
if(s==t)
return 0;
int dis[N]={};
queue<int>q;
q.push(s);

while(!q.empty())
{

int u=q.front();
q.pop();
for(int j=0;prime[j]<u;j++)
{
if(!(u%prime[j]))
{ int v=u+prime[j];
if(dis[v]) continue;
if(v<t){
dis[v]=dis[u]+1;
q.push(v);
}

else if(v==t)
{
return dis[u]+1;
}
else break;

}
}
}
return -1;
}
int main()
{
sieve();
int s,t,cs=1;
while(cin>>s>>t &&s &&t)
{

cout<<“Case “<<cs++<<“: “<<bfs(s,t)<<endl;
}
return 0;
}

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized, uva and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s