枚举算法——大道至简

中国大学MOOC 北京交通大学 算法设计与问题求解

题目描述

李老师的lucky number 是3，5和7，他爱屋及乌，还把所有质因数只有3，5，7的数字也认定为lucky number，比如9, 15, 21, 25等等。请聪明的你帮忙算一算小于等于x的lucky number有多少个？

输入数据 一个正整数x，3 =< x <= 1000000000000

输出数据 小于等于x的lucky number的个数。

样例输入 49

样例输出 11

#include<iostream> #include<cmath> typedef long long ll; using namespace std; int main(){ ll num; int ans = 0; cin>>num; for(ll i=0;i<num/3+1;++i){ for(ll j=0;j<num/5+1;++j){ for (ll k=0;k<num/7+1;++k){ if((pow(3,i)*pow(5,j)*pow(7,k))<=num && (i+j+k>0)){ ans += 1; } } } } cout<<ans<<endl; return 0; }

思想: 运用枚举算法，三重循环遍历，由于三个因数互质，每个变量从零开始枚举，满足要求即可，i+j+k条件用于排除1的情形！