好吧,最后让我们用C来实现,看看再能榨取多少性能。注意我没有改变算法,C的算法和之前的3种都是基本相同的:

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

typedef unsigned long long ULL;

//if failed return 0
ULL sieve(ULL n)
{
    char *a = malloc(n+1);
    if(!a) return 0;
    memset(a,0,n+1);
    ULL max = sqrtl(n);
    ULL p = 2;
    while(p <= max){
        for(ULL i=2*p;i<=n;i+=p)
            a[i] = 1;
        while(a[++p]); /* empty */
    }
    while(a[n]) n--;
    return n;
}

int main(int argc,char **argv)
{
    ULL n = 0;
    if(argc < 2){
        printf("usage %s n\n",argv[0]);
        return 1;
    }
    sscanf(argv[1],"%llu",&n);
    if(n == 0){
        puts("wrong number format");
        return 2;
    }
    else if(n < 0){
        puts("must + number");
        return 3;
    }

    int start = clock();
    ULL result = sieve(n);
    if(!result){
        puts("sieve calc failed!");
        return 4;
    }
    double end = ((1.0 * (clock() - start)) / CLOCKS_PER_SEC) * 1000.0;
    printf("max p is %llu (take %f ms)\n",result,end);
    return 0;
}

结果只比浏览器版的js稍慢一点,可见浏览器js优化的效果之好。不过C的计算非常稳定,不像浏览器中的js多次计算后性能急剧下降。

05-11 09:21