算法题每日一练---第9天：第几个幸运数字

一、问题描述

到 X 星球旅行的游客都被发给一个整数，作为游客编号。

X 星的国王有个怪癖，他只喜欢数字 3，5和 7。

国王规定，游客的编号如果只含有因子：3，5，7就可以获得一份奖品。

我们来看前 10 个幸运数字是：

3 5 7 9 15 21 25 27 35 45

因而第 11 个幸运数字是： 49

小明领到了一个幸运数字 59084709587505，他去领奖的时候，人家要求他准确地说出这是第几个幸运数字，否则领不到奖品。

请你帮小明计算一下，59084709587505是第几个幸运数字。

二、题目要求

考察

for循环，数学思想
建议用时5~15min

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

三、问题分析

首先，编号只能含有3，5，7这三个因子的话。一开始我想使用for循环，把从1到59084709587505中间的数字一个个判断。

后来发现不行，一个问题是规模太大没法彻底解决问题，另一个无法计算是否只含有3，5，7这三个数字。

后来，我又想到了另一个思路，就是既然你只含有3，5，7，那我就判断这个数由几个3，5，7相乘得到，只要这个数小于目标数字，那么初始定义的sum=0，计数器sum++，最后输出结果。

拓展：

• 头文件#include里面的pow(2,k)，可以计算2的k次方
• 目标数字太大，超出int存储范围，更改为long longg int 存储

四、编码实现

#include <iostream>#include<math.h>//pow的头文件 usingnamespacestd;
intmain()
{
inti,j,k,sum=0;//初始化 longlongintn=59084709587505;//目标数字太大，超出int存储范围，更改为long longg int 存储for(i=0;pow(3,i)<=n;i++)//第一层3的次方     {
for(j=0;pow(5,j)<=n;j++)//第二层5的次方         {
for(k=0;pow(7,k)<=n;k++)//第三层7的次方             {
if(pow(3,i)*pow(5,j)*pow(7,k)<=n)//所有次方相乘小于目标数字                 {
sum++;//sum++                }
            }
        }
    }
cout<<sum-1;//因为0 0 0这种情况不算在内，去除 return0;
}

五、输出结果

输出结果为：1905