醜數

說法一（ugly number）：把只包含質因子2，3和5的數稱作醜數（Ugly Number）。例如6、8都是醜數，但7、14不是，因為它們包含質因子7。 習慣上我們把1當做是第一個醜數。

說法二(humble number)：對於一給定的素數集合 S = {p1, p2, ..., pK},考慮一個正整數集合，該集合中任一元素的質因數全部屬於S。這個正整數集合包括，p1、p1*p2、p1*p1、p1*p2*p3...(還有其它)。該集合被稱為S集合的“醜數集合”。

基本介紹

• 中文名：醜數
• 外文名：Ugly Number、Humble Number

醜數描述

說法一：把只包含質因子2、3和5的數稱作醜數（Ugly Number）。例如6、8都是醜數，但7、14不是，因為它們包含質因子7。 習慣上我們把1當做是第一個醜數。

前20個醜數為：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36。

說法二：對於一給定的素數集合 S = {p1, p2, ..., pK},考慮一個正整數集合，該集合中任一元素的質因數全部屬於S。這個正整數集合包括，p1、p1*p2、p1*p1、p1*p2*p3...(還有其它)。該集合被稱為S集合的“醜數集合”。注意：我們認為1不是一個醜數，醜數集合中每個數從小到大排列，每個醜數都是素數集合中的數的乘積。（如S={2，3，5}時，對應醜數集合為U={2，3，4，5，6，9，10，15，25，30}）

判斷方法

說法一：首先除2，直到不能整除為止，然後除5到不能整除為止，然後除3直到不能整除為止。最終判斷剩餘的數字是否為1，如果是1則為醜數，否則不是醜數。

c++代碼（第n個醜數）

#include <iostream>#include<queue>#include<vector>#include<set>using namespace std;typedef long long ll;const int coeff[3]={2,3,5};int main(){    priority_queue<ll,vector<ll>,greater<ll> > pq;    set<ll> s;    int n；    cin>>n；    pq.push(1);    s.insert(1);        for(int i=1;;i++)         {        ll x=pq.top();pq.pop();                 if(i==n)         {                     cout<<x<<<<endl;                      break;        }                     for(int j=0;j<3;j++)             {            ll x2=x*coeff[j];                         if(!s.count(x2))                  {                s.insert(x2);pq.push(x2);                              }                          }                      }                  }

說法二：c++代碼：（用於查找醜數集合中的第n大的數）

#include<cstdio>    int n,m;        int a[101],b[101];        int s[100001];    int main()    {        scanf("%d %d",&n,&m);        for(int i=1;i<=n;i++)            scanf("%d",&a[i]);    s[0]=1;        for(int i=1;i<=m;i++)    {            int min=2147483647;            for(int j=1;j<=n;j++)        {                        while(a[j]*s[b[j]]<=s[i-1]) b[j]++;                        if(a[j]*s[b[j]]<min) min=a[j]*s[b[j]];        }        s[i]=min;    }                printf("%d",s[m]);}