#include<bits/stdc++.h>
using namespace std;
long long int minhh(long long int a,long long int b,long long int c,long long int d)
{
if(a<=b&&a<=c&&a<=d)return a;
if(b<=a&&b<=c&&b<=d)return b;
if(c<=b&&c<=a&&c<=d)return c;
if(d<=b&&d<=c&&d<=a)return d;
}
int main()
{ long long int dp[10001];
memset(dp,0,sizeof(dp));//多组数据可以沿用前面数据的计算结果
int i,n,u;long long int m1,m2,m3,m4;
for(i=1;i<=10;i++)
{
dp[i]=i;
}u=10;//初始化前10个丑数作为基础
while(scanf("%d",&n),n)
{
if(n<=u)printf("%d\n",dp[n]);
else
{
while(u<n)
{
for(i=1;i<u;i++)
{
if(dp[i]*2<=dp[u])m1=dp[i+1]*2;
if(dp[i]*3<=dp[u])m2=dp[i+1]*3;
if(dp[i]*5<=dp[u])m3=dp[i+1]*5;
if(dp[i]*7<=dp[u])m4=dp[i+1]*7;
}
u++;
dp[u]=minhh(m1,m2,m3,m4);
}
printf("%d\n",dp[n]);
}
}
return 0;
}
总结
1.调用函数时，要确保返回值和接受用的变量时同意类型，特别是程序写到一半，调试时发现数据溢出，把int换成long long int的时候
2.要正确理解题意，正确的题意应该是每一个丑数都是由2，3，5，7互相相乘出来的，思路就是，用 dp数组保存已经求出的丑数，然后遍历数组，分别找出乘以2，3，5，7之后比当前最大丑数大的丑数，显然它们之中最小的那个就是新的丑数（因为找不到比它更小，同时又比当前最大丑数大的丑数了）
我一开始理解成只能含2，3，5，7这四个素数因子，所以应该是除了1和这四个素数因子之外的素数，以及它们的倍数都不是丑数，其他都是丑数，于是想每遇到一个数就判断是否是素数或者它的倍数，这样也能求出正确答案，但程序效率太低
错误案例
#include<bits/stdc++.h>
using namespace std;
int dp[10000000001];
int main()
{
//memset(dp,0,sizeof(dp));多组数据可以沿用前面数据的计算结果
int i,j,n,t,prime=0;
while(scanf("%d",&n),n)
{
if(n<=10)printf("%d\n",n);
else
{
for(i=11;i<=n;i++)
{
t=1;
for(j=0;j<prime;j++)
{
if(i<dp[j])break;
else if(!(i%dp[j])){t=0;n+=1;break;}//素数的倍数，n向后一个数
}
if(t)
{
if(t)for(j=2;j<=sqrt(i);j++)//注意判断i是否是素数是从2开始，到i-1结束
{
if(!(i%j)){t=0;break;}//判断是否为素数
}
if(t){n+=1;dp[prime]=i;prime+=1;}
}
}printf("%d\n",n);
}
}
return 0;
}
