P4396 与3和5无关的数（入门）

解题思路

先弄明白"相关"和"无关"：题目说，一个数是 3 的倍数或者 5 的倍数，就叫做"与 3 和 5 相关的数"。反过来，"与 3 和 5 无关"就是：既不是 3 的倍数，也不是 5 的倍数。比如 3 是 3 的倍数所以相关，5 是 5 的倍数所以相关，15 两个都是所以相关，而 7 既不是 3 的倍数也不是 5 的倍数，所以无关。

所以从 1 到 n 一个一个检查，判断条件就是 i % 3 != 0 && i % 5 != 0，满足就输出这个数并计数。

拿样例 n=20 验证：1 到 20 里面，与 3 和 5 都无关的有 1、2、4、7、8、11、13、14、16、17、19，一共 11 个数。第一行输出这些数，第二行输出 11，和样例一致。

边界情况：n 最小是 1，1 既不是 3 的倍数也不是 5 的倍数，所以至少会输出 1。要注意 15 这样的数既是 3 的倍数也是 5 的倍数，判断"相关"用"或"，判断"无关"必须两个条件同时满足，用 &&。输出时第一行数字之间用空格隔开，最后再换行输出个数。

参考代码

// 程序用途：输出1~n之间与3和5都无关的数，并统计个数
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt = 0;                      // cnt统计满足条件的个数
    for (int i = 1; i <= n; i++) {
        if (i % 3 != 0 && i % 5 != 0) {   // 既不是3的倍数也不是5的倍数
            if (cnt > 0) cout << " ";     // 除第一个数外，前面加空格
            cout << i;
            cnt++;
        }
    }
    cout << endl << cnt << endl;      // 第一行数字，第二行个数
    return 0;
}

复杂度分析

从 1 循环到 n，n 最大是 100，时间复杂度是 O(n)；空间上只用了计数变量，额外空间复杂度是 O(1)。