ACM Q 443：Humber Number

Humble Number

第一種解法

i=1～20,000,000,000 每一個數值去除 2、 3、 5、 7，如果除完後，若數值為1。就表示該數字為Humble Number。

#include<stdio.h>

#include<stdlib.h>

main(){

      int Hum[5844],i=1,j=2,m;

      Hum[0]=1;

      while(i<=5841){

         m=j;

         while(m%2==0){m=m/2;if(m%10==0)m=m/10;if(m%14==0)m=m/14;if(m%32==0)m=m/32;if(m%128==0)m=m/128;if(m%8==0)m=m/8;}

         while(m%3==0){m=m/3;if(m%9==0)m=m/9;if(m%27==0)m=m/27;}

         while(m%5==0){m=m/5;if(m%25==0)m=m/25;if(m%125==0)m=m/125;}

         while(m%7==0){m=m/7;if(m%49==0)m=m/49;if(m%343==0)m=m/343;}

         if(m==1) {Hum[i]=j;i++;printf("第%i項humble number 是%10d\n",i,j);}

         j++;

      system("PAUSE");system("PAUSE");system("PAUSE");

第二種解法

Humber Number= （2^x ）* （3^y）* （5^z） *（7^m），四個迴圈去解出x,y,z,m

此題跟 Problem 136 Ugly Numbers，簡直一模一樣，只是這一次要求出前 5842 個只有 2 或 3 或 5 或 7 的質因數的數字。這裡不多說，程式碼如下：

int humble[5843];

int min(int a, int b)
{
    return a > b ? b : a;
}

void create()
{
    int num = 0, p2, p3, p5, p7, n;
    humble[1] = p2 = p3 = p5 = p7 = n = 1;
    while (1)
    {
        humble[++ n] = min(2 * humble[p2], 
                       min(3 * humble[p3], 
                       min(5 * humble[p5], 7 * humble[p7]) ));
        if (humble[n] == 2 * humble[p2]) p2 ++;
        if (humble[n] == 3 * humble[p3]) p3 ++;
        if (humble[n] == 5 * humble[p5]) p5 ++;
        if (humble[n] == 7 * humble[p7]) p7 ++;
        if (n == 5842) break;
    }
}

void printNumber(int n)
{
    int s = n % 10;
    int h = n % 100;
    printf("The %d", n);
    if (h == 11) printf("th");
    else if (h == 12) printf("th"); 
    else if (h == 13) printf("th"); 
    else if (s == 1) printf("st");
    else if (s == 2) printf("nd");
    else if (s == 3) printf("rd");
    else printf("th"); 
    printf(" humble number is %d.\n", humble[n]);
}

int main()
{
    create();
    int n;
    while (scanf("%d", &n) == 1 && n)
    {
        printNumber(n);
    }
    return 0;
}