c - c 中的 pow() 函数会产生截断(或舍入)错误？

Question

大家好:我正在使用 pow() 函数来计算素数的幂。但是有些输出没有按预期显示。例如，当我输入 200 时，我希望打印出所有不超过 200 的素数及其幂。 大多数数字都很好，但我注意到有些数字与正确数字相差 1(24 应该是 25,120 应该是 121,124 应该是 125,168 应该是 169)。我在这里遗漏了什么吗？我的平台是运行 Coding::Blocks GNUGCC 的 win7编译器。有什么建议吗？非常感谢...

60
2 3 4 5 7 8 9 11 13 16 17 19 23 24 27 29 31 32 37 41 43 47 49 53 59 61 64 67 71 73 79 81 83 89 97 101 103 107 109 113 120 124 127 128 131 137 139 149 151 157 163 167 168 173 179 181 191 193 197 199

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>

bool is_primes[1000]= {true};
int primes[200]= {0};
int answer[1000]= {0};

void sieve_of_Eratosthenes (bool ary[],int);
void swap(int*,int*);
void quick_sort(int array[], int, int);

int main(int argc,char* argv[]) {
    int n =0,i = 0,j = 0,cnt = 0,temp = 1;

    memset(is_primes,true,sizeof(is_primes));
    memset(primes,0,sizeof(primes));
    memset(answer,0,sizeof(answer));

    sieve_of_Eratosthenes(is_primes,1000);

   //build primes table
   for(i=0; i<1000; ++i) {
       if(is_primes[i]) {
           primes[j++] = i;
       }
   }

   while(scanf("%d",&n)==1) {
       i = 0,j = 0,cnt = 0,temp = 1;

       //primes
       for(j=0,cnt=0;primes[j]!=0; ++j) {
           if(primes[j]<=n) {
            answer[cnt] = primes[j];
            ++cnt;
           }
       }

       //and power of primes
       for(j=0; primes[j]!=0; ++j) {
           for(temp=2;pow(primes[j],temp)<=n;) {
               answer[cnt] = pow(primes[j],temp);
               ++temp;
               ++cnt;
           }
       }

       //sort ascending
       quick_sort(answer,0,cnt-1);

       printf("%d\n",cnt);

       for(j=0; j<cnt; ++j) {
           printf("%d ",answer[j]);
       }

       printf("\n");
    }

    return 0;
}

void sieve_of_Eratosthenes (bool ary[],int n) {
    int i = 0,j = 0;
    is_primes[0] = is_primes[1] = false;
    for(i=2; i*i<=n; ++i) {
        if(is_primes[i]) {
            for(j=i*i; j<=n; j+=i) {
                is_primes[j] = false;
            }
        }
    }
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// sort interval [left, right]
void quick_sort(int array[], int left, int right) {
    if (left < right) {
    // divide (partition)
        int pivot = array[(left+right)/2];
        int i = left - 1, j = right + 1;
        while (i < j) {
            do ++i;
            while (array[i] < pivot);
            do --j;
            while (array[j] > pivot);
            if (i < j) swap(&array[i], &array[j]);
    }

    // then conquer
    quick_sort(array, left, i-1);
    quick_sort(array, j+1, right);

    // no need to combine sub-solutions
    }
}

Answer 1

如果您不知道 pow，您可能会以不同的方式编写该循环:

for(temp = primes[j]*primes[j];
    temp <= n;
    temp *= primes[j]) {
  answer[cnt++] = temp;
}

这不仅可以避免舍入问题；它也会快很多。 (有可能想出一个比 temp 更好的变量名。)