Given a number k, find the smallest Fibonacci number f that shares a common factor d( other than 1 ) with it.
1) For each fibonacci number f in [2,k] , find smallest common factor, findSCF(k,f) = d
2) if d > 1 print f and d
3) else continue until you get your f and d.
4) If fibonacci no not found in [2,k], keep looking for f in [k,infinity) until f%k == 0.
big findSCF(big a, big b) {
if(a%2==0 && b%2==0) return 2;
for(big i = 3; i <= b; i+=2)
if(a%i==0 && b%i==0) return i;
return 1;
}
big f = 2, prev = 1, temp, d=1;
while(f<=k) {
d=findSCF(k,f);
if(d>1) break;
temp=prev;
prev=f;
f+=temp;
}
if(d > 1)
cout << f << " " << d << endl;
else {
while(f%k!=0) {
temp=prev;
prev=f;
f+=temp;
}
cout << f << " " << k << endl;
}
Also check http://www.yourguidetoprogramming.in/2012/07/interview-street-amazon-coding_03.html
Read full article from Just Programming...: Interviewstreet Fibonacci Factor - Amazon India Coding Challenge : Solution C++
1) For each fibonacci number f in [2,k] , find smallest common factor, findSCF(k,f) = d
2) if d > 1 print f and d
3) else continue until you get your f and d.
4) If fibonacci no not found in [2,k], keep looking for f in [k,infinity) until f%k == 0.
big findSCF(big a, big b) {
if(a%2==0 && b%2==0) return 2;
for(big i = 3; i <= b; i+=2)
if(a%i==0 && b%i==0) return i;
return 1;
}
big f = 2, prev = 1, temp, d=1;
while(f<=k) {
d=findSCF(k,f);
if(d>1) break;
temp=prev;
prev=f;
f+=temp;
}
if(d > 1)
cout << f << " " << d << endl;
else {
while(f%k!=0) {
temp=prev;
prev=f;
f+=temp;
}
cout << f << " " << k << endl;
}
Also check http://www.yourguidetoprogramming.in/2012/07/interview-street-amazon-coding_03.html
Read full article from Just Programming...: Interviewstreet Fibonacci Factor - Amazon India Coding Challenge : Solution C++
