好吧,最后让我们用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多次计算后性能急剧下降。