C++中memset()与std::fill()的区别及筛法代码问题求助

memset 和 std::fill 的核心区别 #

• 操作单位不同：
  • memset 是字节级初始化函数，它会把内存区域的每一个字节都设置成指定数值。
  • std::fill 是元素级初始化函数，它会把数组/容器的每一个元素直接赋值为指定值。
• 适用场景不同：
  • memset 适合初始化字节类型（char、unsigned char），或者给数组清零（因为0的每个字节都是0）；但对多字节类型（如int、long long）赋值非0值时，会出现不符合预期的结果。
  • std::fill 适用于所有支持赋值操作的数据类型，包括整数、浮点数、自定义类对象等，能保证每个元素被正确设置为目标值。

你的代码问题所在 #

你定义的数组 s 是 long long 类型（通常占8字节），调用 memset(s,1,sizeof(s)) 时，会把每个 long long 元素的8个字节都设置为 0x01，最终每个元素的实际值是 0x0101010101010101，转换成十进制就是你看到的异常数字 72340172838076673，而非你想要的数值1。

因为这个值不等于1，后续筛法中 if(s[i] == 1) 的判断永远不成立，筛法逻辑完全没有执行，所以输出的都是这个异常值。而改用 std::fill 时，会把每个 long long 元素直接赋值为1，逻辑就能正常运行。

修正方案 #

方案1：使用 std::fill 初始化 #

把 memset(s,1,sizeof(s)) 替换为：

std::fill(s, s + 2000009, 1LL);

这里的 1LL 确保赋值的是 long long 类型的1，避免类型不匹配。

方案2：改用 char 类型数组（更节省内存） #

因为筛法只需要0/1标记是否为质数，用char类型足够，此时可以正常使用memset：

char s[2000009]; // 将long long改为char
void seive(int N) {
    j = 1;
    memset(s, 1, sizeof(s)); // 每个char字节设为1，对应数值1
    s[0] = 0;
    s[1] = 0;
    // 后续逻辑不变
}

修正后的完整代码（方案1示例） #

#include <bits/stdc++.h>
using namespace std;
long long s[2000009], a[1000009], i, j, n;
void seive(int N) {
    j = 1;
    fill(s, s + 2000009, 1LL);
    s[0] = 0;
    s[1] = 0;
    for(int i = 2; i <= sqrt(N); i++) {
        if(s[i] == 1)
            for(int j = i * i; j <= N; j += i) {
                s[j] = 0;
            }
    }
}

int main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n;
    seive(2000000); // 建议直接写2000000，避免浮点数转整数的潜在问题
    for (i = 1 ; i <= n ; i++) {
       cin>>a[i];
       cout<<s[a[i]]<<'\n';
    }
}

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