>>757 を弄ってみた。アーキテクチャによっては低速化
#define BIT_SET(index) (furui[index/32]|=1<<(index&31))
#define BIT_GET(index) ((furui[index/32]>>(index&31))&1)
int sosuu_count(int max){
unsigned long *furui;
int search_max = sqrt(max);
int i, work, num_sosuu;

if ((furui = (unsigned long*)calloc((max/32 + 1), sizeof(*furui))) == NULL){
fprintf(stderr, "malloc error\n");
return -1;
}

/* 0と1は素数ではない */
BIT_SET(0);
BIT_SET(1);

/* 以降は奇数のみ吟味する */
/* 3, 5, 7… */
for (i = 3; i<=search_max; i+=2){
if (BIT_GET(i) == 0){
/* 3倍、5倍、7倍… */
for(work = i*3; work <= max; work+=i*2) BIT_SET(work);
}
}

num_sosuu=1;
for (i = 3; i<=max; i+=2) num_sosuu+=!BIT_GET(i);
free(furui);

return num_sosuu;
}