c - 为什么对某些非素数的素数检查返回真？

Question

我在检查一个数字是否为素数的函数时遇到了问题 - 它有时会返回一个数字不是素数（有时也是偶数！）。知道为什么吗？

int isPrime(long x){
    int i;

    if(x==2||x==3)      return 1;   //if i = 2 or 3, return true
    if(!(x&1))          return 0;   //if x is even  return false

    for(i=3;i<=sqrt(x);i+=2) if (x%i == 0) return 0;        //if x is divisible by i return false

    return 1;
}

对于大家，非常感谢您的回答，如果我的代表足够高，我会全部+1：D

可悲的是，我的白痴达到了新的高度，我发现错误在我程序的其他地方的逻辑中。

Answer 1

可能是因为sqrt(x)这个函数调用的结果是浮点值的舍入。所以它可能比四舍五入到最接近的整数略小。

在这种情况下，例如sqrt(25)可以四舍五入4而不是5.

编辑

故障编号104730说明

 if(!(x&1)) return 0;   //if x is even  return false

似乎无法正常工作...那么，您可以尝试一下x&1L吗？

我不确定，但 id 和的大小int不同long，并且（可能）1隐式地被强制转换为较短的一种类型，所以它可能检查不正确的位......

也试试

if(!(x%2)) return 0;   //if x is even  return false

为了避免位模式的使用和平台依赖性。

Answer 2

我将for循环编辑为：

for(i=3;i<=x/2;i+=1) if (x%i == 0) return 0; 

我主要通过前 100 个数字。

int main()
{
    long test=0;
    int i = 2;
    for( ; i < 100; i++)
    {
        test = isPrime(i);
        if(test == 1) printf("%d ",i);
    }

       getchar();
       return 0;
}

这是输出：这是前 100 个素数的输出：

2 3 5 7 11  13  17 19 23 29  31 37 41 43 47  53 59 61 67 71  73 79 83 89 97

我将其更改i+=2为i+=1，因为在您的代码中每隔一秒跳过一次数字。

Answer 3

您没有检查是否x可被 2 整除。

在该for循环之前添加一个return 0如果它可以被 2 整除。