Solution of Light OJ 1141 - Number Transformation

/* Bismillar Rahmanir Rahmanir Solution-Using BFS */ #include<bits/stdc++.h> using namespace std; vector<int>p_fact[1001]; int prime[200], t_case, t=1, a, b, cnt=0,ans, sz; bool num[501]; void sieve(){ for(int i=0; i<=500; i++)num[i]=true; for(int i=3; i*i<=500; i+=2){ if(num[i]){ for(int j=i*i; j<=500; j+=i*2) num[j]=false; } } int j=0; prime[j++]=2; for(int i=3; i<=500; i+=2){ if(num[i]){ cnt++; prime[j++]=i; } } } void prime_fact(){ //store the prime fact in every index number for(int i=0; i<cnt; i++){ for(int j=2; j*prime[i]<=1000; j++) p_fact[j*prime[i]].push_back(prime[i]); } } bool bfs(int x, int y){ int level[1009]={0}, xx, xxx; bool visit[1001]; memset(visit, false, sizeof(visit)); queue<int>q; q.push(x); level[x]=0; while(!q.empty()){ xx=q.front(); if(xx==y){ans=level[xx]; return true;} q.pop(); sz=p_fact[xx].size(); if(!visit[xx]){ for(int i=0; i<sz; i++){ xxx=xx+p_fact[xx][i]; if(xxx<=y){ if(!level[xxx]) level[xxx]=level[xx]+1; q.push(xxx); } if(xxx==y){ ans=level[xxx]; return true; } } visit[xx]=true; } } return false; } int main() { sieve(); prime_fact(); cin>>t_case; while(t_case--){ cin>>a>>b; if(bfs(a, b)) cout<<"Case "<<t++<<": "<<ans<<endl; else cout<<"Case "<<t++<<": -1"<<endl; } return 0; }