我們刷題時提交代碼看到【Time Limit Error】都多多少少有點憂愁，

寫這篇文章的起因是，我前幾天刷題刷到了兩道都是關于平方數的題目，第一道是浙江理工大學12月5號舉辦的線上新生賽的B題，第二道是國外網站Codeforces12月20號舉辦的一場比賽也是B題，并且都是如果不進行演算法優化，一定會超時，這就不得不讓我做一個總結，題目并不是很難，歡迎大家一起交流～

#include<stdio.h>
#include<math.h>
int count(int n, int arr[])
{
	int i = 0, count = 0;
	for (int i = 1; i <= 320;i++)
	{
		if (n%arr[i] == 0)
			count++;
//這個地方就實作了由判斷一個數的因子是否為平方數轉化為判斷所涉及范圍內所有平方數是否是其因子,
//避免了找因子的繁瑣步驟,大大減少了運行時間，
//在演算法競賽中，可以解決平方數相關問題因引數太大而產生的超時問題，
		if (arr[i] > n)
			break;
	}
	return count;
}
int is_prime(int n)
{
	int i = 0;
	for (i = 2; i < n; i++)
	{
		if (n%i == 0)
			return 0;
//回傳0,為非素數
	}
	return 1;
//回傳1,為素數，
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int arr[321];
//存平方數，因為題目n最大值為100000,所以只需要從1存到100000范圍內的平方數即可,
//100000開方等于316.227766...,所以我們至少要存316個平方數，
//為了避免越界訪問，不妨把陣列開到321,存下320個平方數，
	for (int i = 1; i <= 320; i++)
	{
			arr[i] = i*i;
	}
	int sum = 0;
	for (int i = 1; i <= n; i++)
//依據題意逐一統計1~n中的每一個數有多少因子是平方數，即有多少平方因子，
	{
		if (is_prime(i))
			sum++;
//為了進一步節省時間，我們可以先把過濾掉素數,因為素數的平方因子都僅有一個，
		else
			sum += count(i,arr);
//這里用一個函式統計一個數有多少平方因子，
	}
	printf("%d", sum);
	return 0;
}

國外的刷題網站顯示的都是英文，我一般用網易有道詞典翻譯，這里附上譯文：

平方數和立方數
時間限制每個測驗1秒，
記憶體限制每個測驗256MB，
Polycarp喜歡正整數的平方和立方，這是他喜歡的數字序列的開頭:1、4、8、9，....
對于給定的數字n，數數Polycarp喜歡的從1到n的整數個數，
換句話說，找出這樣的x的個數，x是一個正整數的平方或一個正整數的立方(或同時是一個平方和一個立方)，
輸入
第一行包含一個整數t(1≤t≤20) - 測驗用例的數量，
然后t行包含測驗用例，每行一個，每一行包含一個整數n(1≤n≤10^9)，
輸出
對于每個測驗用例，輸出您想要的答案—Polycarp喜歡的從1到n的整數的數目，

#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{
	int t;
	scanf("%d", &t);
	int arr1[32002];
	for (int i = 1; i <= 32000; i++)
	{
		arr1[i] = i*i;
	}
	//存平方數，因為題目n最大值為1000000000,所以只需要從1存到1000000000范圍內的平方數即可,
	//1000000000開方等于31622.7766...,所以我們至少要存31622個平方數，
	//為了避免越界訪問，不妨把陣列開到32002,存下32000個平方數，
	int arr2[1002];
	for (int j = 1; j <= 1000; j++)
	{
		arr2[j] = j*j*j;
	}
	//存立方數，因為題目n最大值為1000000000,所以只需要從1存到1000000000范圍內的立方數即可,
	//1000000000開立方等于1000,所以我們至少要存1000個平方數，
	//為了避免越界訪問，不妨把陣列開到1002,存下1000個平方數，
	int arr3[1002];
	int x = 1;
	for (int j = 1; j <= 1000; j++)
	{
		int q = pow(arr2[j], 1.0 / 2);
		if (q*q == arr2[j])
		{
			arr3[x] = j*j*j;
			x++;
		}
	}
	//存即是平方數又是立方數，由于立方數最大就是只是1000的立方,所以從立方數中找平方數更加省時，
	while (t--)
	{
		int n = 0;
		int flag1 = 0;
		scanf("%d", &n);
		if (n == 1000000000)
		{
			printf("%d\n", (int)pow(pow(10, 9), 1.0 / 2) + 1000 - x + 1);
			continue;
		}
        //后面我們只需要取比n小的所有平方數,加比n小的所有立方數,再減去即是平方數又是立方數以避免重復，
		for (int i = 1; i <= 32000; i++)
		{
			if (arr1[i] > n)
			{
				flag1 = i - 1;
				break;
			}
		}
		int flag2 = 0;
		for (int i = 1; i <= 1000; i++)
		{
			if (arr2[i] > n)
			{
				flag2 = i - 1;
				break;
			}
		}
		int flag3 = 0;
		for (int i = 1; i <= 1000; i++)
		{
			if (arr3[i] > n)
			{
				flag3 = i - 1;
				break;
			}
			if (i == 1000)
			{
				flag3 = x - 1;
			}
			//因為前面并沒有判斷即是平方數又是立方數的最大值,所以考慮n可能會大于arr3中所有的數，
			//判斷i=1000說明沒有符合arr3[i]>n條件的，所以1~n包括了所有的arr3中的數,前面我們也提前用x統計了arr3中的個數，
		}
		printf("%d\n", flag1 + flag2-flag3);
		//最后輸出1~n中是平方數和立方數的個數，
	}
	return 0;
}

提交后，顯示第一題實際運行時間196ms，第二題實際運行時間15ms，可以滿足題目要求，