一个简单遍历的算法优化

前几天一个学弟问了我一个C语言的循环遍历的题，其中，题目是这样的：

一个小于10万的正整数，它加上100后是一个完全平方数（即一个数的平方），再加上168又是一个完全平方数，请问该数是多少？提示：不一定只有一个。要求：使用for循环语句和条件语句解决此问题。

普通解法：

#include <stdio.h>
#include <math.h>

#define N 100000

int main()
{
	int number=0,temp1, temp2;
	for(number=1;number<N;number++)
	{
		temp1 = number + 100;//第一个数 
		temp2 = number + 268;//第二个数 
		int a = sqrt(temp1), b = sqrt(temp2);
		if(temp1==a*a&&temp2==b*b)
			printf("%d\n",number); 
	}
	return 0;
} 
           

刚开始以为这已经算行了，但是在想了想过后，若是不是求加100再加168等等呢，万一要求的范围是一亿呢？如果还是使用遍历无疑这个程序的时间复杂度会很大，所以优化了一个过后：

#include <stdio.h>
#include <math.h>

#define N 100000

int main()
{
 	int num=0,temp=0;
    for(num=10;num<sqrt(N);num++)
    {
	     temp = num*num+168;
	     if((int)sqrt(temp)*(int)sqrt(temp)==temp) 
	     printf("%d\n",num*num-100);
    }
   return 0;
}

           

在经过测试后，在范围为一亿的时候时间差距开始显现，普通的需要1.2s左右，优化过后的只需要0.2s左右，当改变一定条件过后，

#include <stdio.h>
#include <math.h>

#define N 100000000

int main()
{
	printf("这是%d的普通版\n",N);
	int number=0,temp1, temp2;
	for(number=1;number<N;number++)
	{
		temp1 = number + 586;//第一个数 
		temp2 = number + 685;//第二个数 
		int a = sqrt(temp1), b = sqrt(temp2);
		if(temp1==a*a&&temp2==b*b)
			printf("%d\n",number); 
	}
	return 0;
} 
           

#include <stdio.h>
#include <math.h>

#define N 1000000000

int main()
{
	printf("这是%d的优化版\n",N);
 	int num=0,temp=0;
    for(num=sqrt(586);num<sqrt(N);num++)
    {
	     temp = num*num+99;
	     if((int)sqrt(temp)*(int)sqrt(temp)==temp) 
	     printf("%d\n",num*num-586);
    }
   
   return 0;
}
           

结果如下：

虽然这是一次小的优化，但是自己感觉还是很好！