c中的eratosthenes筛选

Question

这是我在C中筛选eratosthenes的代码.它给了我以下输出.

2 3 5 7 11 13 17 19 23 25 31 35 37 41 43 47

我的输出包括25和35也不是素数,它不包括29.

谁能告诉我哪里错了.

#include<stdio.h>
#include<math.h>
int main()
{
    int i,a[50],b[50],j,n=0,s;
    for(i=0;i<50;i++)
        a[i] = 1;
    a[0]=a[1] = 0;

    for(i=2;i<50;i++)
        if(a[i])
            for(j=pow(i,2);j<50;j+=i)
                a[j] = 0;

    for(i=0;i<50;i++)
        if(a[i])
        {
            b[n] = i;
            n++;
        }

    for(j=0;j<n;j++)
        printf("%d\n",b[j]);
    return 0;
}

Answer 1

用gcc版本4.4.7(Ubuntu/Linaro 4.4.7-2ubuntu1)编译,你的代码返回正确的结果.该问题可能与编译器和pow()实现有关.

也许你有一个天真的执行pow,计算pow(x,y)为exp(y*log(x)).这是浮点运算,它遇到常见的浮点问题.这意味着pow(x,y)转换为整数的结果将被截断,因为双算术log(x)*y和取幂将返回略小于整数的double值x*y.

将代码更改为

for( j = i * i; j < 50; j += i)
    a[j] = 0;

另外,我们只能迭代直到sqrt(n),因为第二个循环才会被执行:

for( i = 2; i < sqrt(50); i++)
    if( a[i]) // if not marked
        /* mark starting from i*i because i*j for j<i
         * has been already marked when i was j */
        for( j = i * i; j < 50; j += i)
            a[j] = 0; 

相关问题:代码块功率功能在c中不起作用