好吧问答库 > c++求丑数程序的优化（第一行输入整数T，表示求多少次然后输入T个整数n。）

c++求丑数程序的优化（第一行输入整数T，表示求多少次然后输入T个整数n。）

bool isprime1(int num) { bool flag = true; for (int i = 2; i < num; i++) {//除2，3，5以外的素数 if (num%i == 0) { flag = false; break; } } return flag;}void task1047() { int ci,num; cin >> ci; for (int i = 1; i <= ci; i++) {//ci：执行几次 cin >> num; //求第几位数 if (num <= 6) {//小于6时 cout << num; } else { //大于6时 int Num = 6; for (int i = 7;; i++) {//数字从7到n； for (int n=7; n <= i; n++) {//大于等于7的素数 if (isprime(n)&&i%n==0) { break; } if (n == i) { Num++; //第Num个丑数 if (Num == num) { cout << i<<endl; } } } if (Num == num) { break; } } } }}int main() { task1047(); return 0;}结果正确，但OJ平台显示time limit exceeded，我该如何解决呀？

2026年09月25日 23:09

有1个网友回答

网友（1）：

你这个属于暴力穷举，基本上不到100就要以秒计了，肯定超时

以前写过一个，主动产生丑数的算法,第1000个也就是1毫秒以内

算法的主要精神就是：后面的丑数是由前面的丑数*2，*3或者*5得来的，然后主动生成丑数序列，关于丑数算法具体细节原理，网上有很多文章，你可以自己搜索

#include   
#include 
using namespace std;
int min(int a, int b, int c)
{
	int t = a < b ? a : b;
	return t }
int uglnum(int n)
{
	int* unum = new int[n];
	int un,i, i2, i3, i5;
	unum[0] = 1;
	i2 = i3 = i5 = 0;
	for (i = 1; i < n; ++i)
	{
		un = min(unum[i2] * 2, unum[i3] * 3, unum[i5] * 5);
		i2 += (un == unum[i2] * 2);
		i3 += (un == unum[i3] * 3);
		i5 += (un == unum[i5] * 5);
		unum[i] = un;
	}
	un = unum[n - 1];
	delete[] unum;
	return un;
}

int main()
{
	int t,n;		
	time_t ts;
	cin >> t;
	for (int i = 0; i < t; ++i)
	{
		cin >> n;
		//ts = clock();
		cout << uglnum(n) << endl;
		//ts = clock() - ts;
		//cout << ts<<"ms"<	}	
	return 0;
}

c++求丑数程序的优化（第一行输入整数T，表示求多少次 然后输入T个整数n。）

c++求丑数程序的优化（第一行输入整数T，表示求多少次然后输入T个整数n。）