一個簡單周遊的算法優化

前幾天一個學弟問了我一個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;
}
           

結果如下：

雖然這是一次小的優化，但是自己感覺還是很好！