java-网易面试题-求Fibonacci数列中第k个与前面所有数互质的数（除前面两个数 1，1 ）

public class KthFibonaciPrime {

	/**
	 * 求Fibonacci数列中第k个与前面所有数互质的数（除前面两个数 1，1 ）
	 * 假设k=1时，2为所求
	 */
	public static void main(String[] args) {

		KthFibonaciPrime k=new KthFibonaciPrime();
		System.out.println(k.getKthRelativelyPrime(5));
	}

	/*
	 * 设fi为Fibonacci数列的第i项
	 * 下面这个方法的问题在于：判断fi是否符合条件时，将fi与前面的i-1个Fibonacci数比较，要分别求出f3,f4,...f(i-1)
	 * 存在重复计算的问题
	 * 是否可以将Fibonacci数列提前算好，并存储在一个数组中？
	 */
	public int getKthRelativelyPrime(int k){
		int count=0;
		int i,j;
		for(i=3;;i++){
			int fi=getFibonaci(i);//判断fi是否与前面的所有Fibonac数互质
			for(j=3;j<i;j++){
				int fj=getFibonaci(j);
				if(!relativelyPrime(fi,fj)){
					break;//继续判断下一个fi是否符合
				}
			}
			if(j==i)count++;
			if(count==k){
				return fi;
			}
		}
	}
	/*
	 *get Nth Fibonaci number
	 *更合理的方法应该是利用矩阵
	 */
	public int getFibonaci(int n){
		if(n==1||n==2){
			return 1;
		}else{
			int n1=1,n2=1;
			for(int i=3;i<=n;i++){
				int tmp=n2;
				n2=n1+n2;
				n1=tmp;
			}
			return n2;
		}
	}
	
	public boolean relativelyPrime(int x,int y){
		return maxFactor(x,y)==1;
	}
	
	//最大公约数  a greatest common denominator
	public int maxFactor(int x,int y){
		if(x<y){
			int tmp=x;
			x=y;
			y=tmp;
		}
		if(x%y==0){
			return y;
		}
		else{
			return maxFactor(y,x%y);
		}
	}
}