java-64.寻找第N个丑数

public class UglyNumber {

	/**
	 * 64.查找第N个丑数
具体思路可参考 [url] http://zhedahht.blog.163.com/blog/static/2541117420094245366965/[/url]
	 * 
题目：我们把只包含因子
2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。

	 */
	public static void main(String[] args) {
		UglyNumber un=new UglyNumber();
		int n=50;
		int re=un.findNthUglyNumber2(n);
		System.out.println(re);
	}

	public int findNthUglyNumber1(int n){
		int count=0;
		int i=1;
		while(count<n){
			if(isUglyNumber(i)){
				count++;
				if(count==n){
					return i;
				}
			}
			i++;
		}
		return -1;
	}
	
	public boolean isUglyNumber(int x){
			while(x%2==0)x/=2;
			while(x%3==0)x/=3;
			while(x%5==0)x/=5;
			return x==1?true:false;
	}
	//like finding a SuShu/PrimeNumber
	public int findNthUglyNumber2(int n){
		int re=-1;
		int[] a=new int[n];
		a[0]=1;
		int p2=0,p3=0,p5=0;
		int i=1;
		while(i<n){
			a[i]=min(a[p2]*2,a[p3]*3,a[p5]*5);
			while(a[p2]*2<=a[i])p2++;
			while(a[p3]*3<=a[i])p3++;
			while(a[p5]*5<=a[i])p5++;
			i++;
		}
		re=a[i-1];
		return re;
	}
	public int min(int a,int b,int c){
		return (a<b?a:b)<c?(a<b?a:b):c;
	}
}