mitbbs- super cool数字

251.  A positive integer is said to  be square  free if it is divisible by no perfect  square 
larger than 1. For example, the first few squarefree numbers are {1,  2, 3, 5, 6, 7, 10, 
11, 13, 14, 15, 17, 19, …}. Find the nth smallest squarefree number. Note n can be very 
large such as 1M.


218. x^n = y, x/n/y 都是整数，n>1，y 叫做一个啥数来着，姑且叫做 Super Cool 数吧, 
比如，1^2 = 1×1=1， 1^3 = 1×1×1 = 1 ...
2^2 = 2×2=4， 2^3 = 2×2×2 = 8 ...
现在给你一个整数 y，请返回最近的那个 Super Cool 数，写 Code。

对每一个小于 sqrt(y)的数，求对数后找一个最接近的即可。。

两题都是出自mitbbs那个pdf文档。

我觉得这样实现貌似对的，虽然没有考虑很大数字问题。

找到根号。

然后递减看看能否整除。不知道是否时间代价会很大。

是否应该只找到是质数的数字除？可那样考虑会很复杂吧。

bool isSuperCool(int y)
{
	if (y<=1)
	{
		return false;
	}
	int sqrt_y=sqrt((double)y);

	for (int k=sqrt_y;k>1;k--)
	{
		int t=y;
		while(t>1)
		{
			if (t%k==0)
			{
				t/=k;
			}
			else
			{
				break;
			}
		}
		if (t==1)
		{
			return true;
		}
	}
	return false;
}