题目的主要信息：

• 输出小于等于n 的与 7 有关数字的个数，包括 7 的倍数，还有包含 7 的数字的个数
• ，有多组输入

方法一：连除法判断

具体做法：

我们可以遍历1到n，对每个数字判断是否与7有关，如果有关则计数，否则跳过进入下一个数字。

每个数字判断的时候，首先判断是否是7的倍数，然后用连除法取余判断是否数字里包含7.

#include<iostream>
using namespace std;

bool select7(int i){
    if(i % 7 == 0) //7的倍数
        return true;
    while(i != 0){ //连除法
        if(i % 10 == 7) //数字里包含7
            return true;
        i /= 10;
    }
    return false;
}
int main(){
    int n;
    while(cin >> n){
        int count = 0;
        for(int i = 1; i <= n; i++) //穷举1到n
            if(select7(i)) //查看是否符合要求
                count++;
        cout << count << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(nlo{g}_{10}n)O(nlog\_\{10\}n)$，遍历n个数字，每个数字检查都是连除法
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：字符串判断

具体做法：

对上述方法一优化，首先7以下的数字不可能与7有关，因此我们的遍历可以从7开始到n。

对于每个数字，要么是7的余数，要么数字里面有7，第一个条件直接判断，第二个条件我们可以将数字转化为字符串，然后用字符串查找函数find找相关字符7.

#include<iostream>
#include<string>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        int count = 0;
        for(int i = 7; i <= n; i++) //枚举7到n
            if(i % 7 == 0 || to_string(i).find('7', 0) != string::npos) //整除7或者转化字符串后能找到字符7
                count++;
        cout << count << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(nlo{g}_{10}n)O(nlog\_\{10\}n)$，字符串长度为$lo{g}_{10}nlog\_\{10\}n$，遍历7到n的每个数字
• 空间复杂度：$O(1)O(1)$，字符串空间为常数空间