推荐订阅源

相信大家都知道什么是humble number.但我还是简短介绍一下，假设一个质数集合{2，3，5，7...}，求一个整数列，他们的共同属性是所有的因子都是那个质数集合里的。现在问题是求给定的第N个这样的整数。如果质数只有3个或4个那么简单的搜索可能就行了，但是当数量很多时就会很耗时，所以可采用下面的方法。

#include<stdio.h>
int main(){
  int h[5842];//表示所求的整数的个数
  int pindex[4]={0};//质数索引
  int prim[4]={2,3,5,7};//质数数组
  int i,j,min;
  h[0]=1;
  for(i=1;i<5842;i++){
    j=0;
    while(j<4){
      if(h[pindex[j]]*prim[j]<=h[i-1])
        pindex[j]++;
      j++;
    }
    min=2000000001;
    for(j=0;j<4;j++){
      if(h[pindex[j]]*prim[j]<min)
        min=h[pindex[j]]*prim[j];
    }
    h[i]=min;
  }
  int n;
  while(scanf("%d",&n)&&n!=0){
    if(n%10==1&&n%100!=11)
      printf("The %dst humble number is %d."n",n,h[n-1]);
    else if(n%10==2&&n%100!=12)
      printf("The %dnd humble number is %d."n",n,h[n-1]);
    else if(n%10==3&&n%100!=13)
      printf("The %drd humble number is %d."n",n,h[n-1]);
    else
      printf("The %dth humble number is %d."n",n,h[n-1]);
  }
}