题意

丑陋数n的意思是n的所有素数因子只有2,3,5。
求出前1500个丑陋数。(第一个丑陋数是1)

思路

用一个数组维护所有的丑陋数。一开始数组中只有一个数就是1。
现在可以确定的丑陋数还有1*2,1*3,1*5。把这三个数中最小的2放进数组。然后变成了2*2,1*3,1*5。再把最小的一个数放进数组…依次执行下去，直到倒数第三个数填满整个丑陋数数组。
用c2 c3 c5确定目前的和2 3 5相乘的丑陋数。

注意判断三个数有相等的情况。

代码

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int maxn = 1510; int s[maxn]; int main() { s[1] = 1; int c2=1,c3=1,c5=1; for(int i = 2 ; i < maxn ; i ++) { //????s[i]???? int s2 = s[c2]*2,s3 = s[c3]*3,s5 = s[c5]*5; if(s2 < s3) { if(s2 < s5) { s[i] = s2; c2 ++; continue; }else if(s2 > s5) { s[i] = s5; c5 ++; continue; }else { s[i] = s5; c2 ++; c5 ++; continue; } }else if(s2 > s3) { if(s3 < s5) { s[i] = s3; c3 ++; continue; }else if(s3 > s5) { s[i] = s5; c5 ++; continue; }else { s[i] = s5; c5 ++; c3 ++; continue; } }else {//s2 = s3 if(s2 < s5) { s[i] = s2; c2 ++; c3 ++; continue; }else if(s2 > s5){ s[i] = s5; c5 ++; continue; }else { s[i] = s2; c2 ++; c3 ++; c5 ++; continue; } } } int n; while(scanf("%d",&n) && n) printf("%d\n",s[n]); return 0; }