紫书习题 10-4 UVa 1644（素数筛）

素数筛没什么好说的

#include<cstdio>

#include<vector>

#include<cstring>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 2123456;

bool is_prime[MAXN];

vector<int> prime;

void init()

{

	memset(is_prime, true, sizeof(is_prime));

	is_prime[0] = is_prime[1] = false;

	REP(i, 2, MAXN)

	{

		if(is_prime[i]) prime.push_back(i);

		REP(j, 0, prime.size())

		{

			if(i * prime[j] >= MAXN) break;

			is_prime[i * prime[j]] = false;

			if(i % prime[j] == 0) break;

		}

	}

}

int solve(int x)

{

	if(is_prime[x]) return 0;

	int i, j;

	for(i = x; !is_prime[i]; i--);

	for(j = x; !is_prime[j]; j++);

	return j - i;

}

int main()

{

	init();

	int n;

	while(~scanf("%d", &n) && n)

		printf("%d\n", solve(n));

	return 0;

}

巴特西

紫书习题 10-4 UVa 1644（素数筛）

最新文章

热门文章

巴特西

紫书 习题 10-4 UVa 1644（素数筛）

最新文章

热门文章

紫书习题 10-4 UVa 1644（素数筛）