前几天在广州去面试游戏开发，其中一道题是素数的算法优化，无奈之下，实在想不出，失败后回家宿舍查找了一下资料，目前最优的应该是（不太确定）初等数论的筛选法，用空间换时间的一种思想。
筛选法的具体的说明：https://blog.csdn.net/yangxjsun/article/details/80201735
位数组实现的具说明：https://blog.csdn.net/qq_37375427/article/details/79797359
下面贴上我的代码：
//VS2017 win10 64位debug //三代i5,计算21亿多以内的素数，用时146秒 #include <stdio.h> #include <stdlib.h> #include <memory.h> #define N _CRT_INT_MAX //int 类型的最大表示，大概21亿多 #include <time.h> #include <math.h> char *init_bin(int n) { char *tem = (char *)malloc(n / 8+1);//分配内容，因为一个字节有8位，每一位表示一个数，多一个字节是怕越界 memset(tem, 0, (n / 8+1)); //清空置0 return tem; } int main() { char *a = init_bin(N); long long i, j; clock_t start, end; start = clock(); for (i = 2; i < N; i++) { if (i % 2) a[i>>3] |= (1<<(i&0x7));//把2的倍数去掉，变为0 } for (i = 3; i < sqrt(N); i++)//把3到根号n质数的倍数去掉 { if (a[i]) { for (j = i + i; j < N; j = j + i) a[j >> 3] &= ~(1 << (j & 0x7)); } } end = clock(); printf("time=%f\n", (double)((end - start) / CLK_TCK));//计算时间 for (i = 0; i < N; i++) { if (a[i >> 3] & (1 << (i & 0x7))) printf("%d %c", i, (i % 10 == 0 )? '\n' : ' '); } system("pause"); return 0; }我的电脑是三代I5,4G win10系统，计算21亿多用了146秒。大伙可以试试
打印比计算还要长时间
附上初等数论原书，唉，后悔专业课没学好
