如何高效统计数组中被标记为True的元素数？优化O(N²)算法

现有一个大小为N、初始化为False的布尔数组，以及一组互不相同的正整数集合S。对于S中的每个元素e，需将数组1索引下能被e整除的位置设为True。例如当N=6、S={2,3}时，结果数组为{0,1,1,1,0,1}（注：数组采用0索引存储，对应1索引的位置1到6）。

现有C++实现代码如下：

bool arr[N]{};
for(int e : S) {
    for(int i = e-1; i < N; i += e) {
        arr[i] = true;
    }
}

该实现可行但效率不足，当S的元素数量可达N时，时间复杂度为O(N²)。由于仅需统计最终数组中True元素的数量，请问是否存在更快的实现方式，时间复杂度最好为O(NlogN)或更优？

有更高效的实现方式，核心是避免对同一位置重复标记，借鉴埃拉托斯特尼筛法的思路，先筛选出S中无需重复处理的核心元素，再进行统计。

具体步骤 #

• 第一步：标记S中的元素
  创建大小为N+1的辅助数组is_in_S，初始化为False，遍历集合S，将is_in_S[e]设为True（仅处理≤N的元素，大于N的元素无对应数组位置，可直接忽略）。
• 第二步：筛除冗余元素
  从1到N遍历每个数x，若is_in_S[x]为True，则将x的所有倍数（2x、3x…≤N）对应的is_in_S设为False。这些倍数属于冗余元素，因为它们的标记范围已被更小的x覆盖，无需单独处理。
• 第三步：统计有效标记数量
  创建大小为N的marked数组（初始为False），遍历所有is_in_S[x]为True的x，从x-1（对应1索引的x）开始，以x为步长遍历数组，将未标记的位置设为True并计数。

C++代码示例 #

int count_true(int N, const vector<int>& S) {
    vector<bool> is_in_S(N + 1, false);
    for (int e : S) {
        if (e <= N) {
            is_in_S[e] = true;
        }
    }

    // 筛除S中为其他元素倍数的冗余元素
    for (int x = 1; x <= N; ++x) {
        if (is_in_S[x]) {
            for (int multiple = 2 * x; multiple <= N; multiple += x) {
                is_in_S[multiple] = false;
            }
        }
    }

    vector<bool> marked(N, false);
    int count = 0;
    for (int x = 1; x <= N; ++x) {
        if (is_in_S[x]) {
            for (int i = x - 1; i < N; i += x) {
                if (!marked[i]) {
                    marked[i] = true;
                    count++;
                }
            }
        }
    }
    return count;
}

复杂度分析 #

该实现的时间复杂度为O(NlogN)：第一步遍历S为O(|S|)，第二步筛除冗余元素和第三步标记统计的复杂度均与埃氏筛一致，为O(NlogN)，整体由O(NlogN)主导，远优于原实现的O(N²)。

可选优化：数学法直接计算 #

若无需构建数组，可基于容斥原理直接计算：先得到经过筛选后的核心元素集合T，计算1到N中至少是T中一个元素倍数的数的个数——对每个元素x计算N/x，减去两两公倍数的个数，加上三三公倍数的个数，以此类推。但当T的元素较多时，容斥的复杂度会指数上升，因此筛法标记的方式更通用。

内容的提问来源于stack exchange，提问作者Mystical