C - 分段筛丢失质数

Question

#include <stdio.h>
#include <math.h>

void sieve(unsigned int up, unsigned int low, unsigned char primes[]);

main()
{
    unsigned int low, up;
    unsigned int steps;
    scanf("%d",&steps);
    for (unsigned int i=0;i<steps;i++){
        scanf("%d %d",&low,&up);

        unsigned char v[up-low];
        sieve (up, low, v);
        for(unsigned int j=0; j<up-low+1; j++){
            if (v[j] == 1){
                printf("%d\n",low+j);
            }
        }   
    }
}
//-------------------------------------------------------------------
void sieve(unsigned int up, unsigned int low, unsigned char primes[])
{
    for (unsigned int i=0;i<up-low+1;i++){
        primes[i]=1;
    }

    for (unsigned int i=2;i<sqrt(up+1);i++) {
        for (int j=((low/i)*i)+i;j<up+1;j+=i){
                primes[j-low] = 0;


        }
    }
}

我正在尝试从特定范围内查找质数。我正在使用 Erastothenes 分段筛，但不幸的是它丢失了一些素数，这是因为:

for (int j=((low/i)*i)+i;j<up+1;j+=i){
                    primes[j-low] = 0;

当 i 变得比我的下限大时，筛选函数开始用 0 值标记质数，毕竟它们不在我的标准输出中。

e.g stdin:
1
2 1000
e.g stdout:
2
37 it loses all prime numbers between 2 and 37
41
43
...

还有一件事，下限值总是被算法识别为素数。

e.g stdin:
4 10

e.g stdout:
4
5
7

我需要一些帮助来调整我的算法以正确标记这个数字，因为几个小时后我真的不知道我需要什么条件才能让它工作。

Answer 1

首先，你有一个差一错误。您的数组不够大，无法容纳所有元素的标志。让它变大:

unsigned char v[up-low+1];

现在主要问题出在你的循环中:

for (unsigned int i=2;i<sqrt(up+1);i++) {
    for (int j=((low/i)*i)+i;j<up+1;j+=i){
        primes[j-low] = 0;
    }
}

您没有从正确的索引开始。在 low==4 的情况下，内循环的第一次迭代将 j 设置为 ((4/2)*2)+2 == ( 2*2)+2 == 4*2 == 6，因此您将完全跳过 4。

保持简单。从 i*2 开始 j。在循环中跳过 j 小于 low 的任何值:

for (unsigned int i=2;i<sqrt(up+1);i++) {
    for (unsigned int j=i*2;j<up+1;j+=i){
        if (j < low) continue;
        primes[j-low] = 0;
    }
}