博客

前几天在广州去面试游戏开发，其中一道题是素数的算法优化，无奈之下，实在想不出，失败后回家宿舍查找了一下资料，目前最优的应该是（不太确定）初等数论的筛选法，用空间换时间的一种思想。

筛选法的具体的说明：

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秒。大伙可以试试

打印比计算还要长时间

附上初等数论原书，唉，后悔专业课没学好