poj3518筛法

/*题意：给出一个数，若为合数则求出其最靠近的两边的质数之差（距离），若是质数，则输出0即可
解题：阿拉斯托散筛法的应用，试模板的题目
63msACc++代码*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include<algorithm>
using namespace std;
long n = 1299999;
bool visit[10100000];
long  prime[10000000];
void init_prim()
{
memset(visit, true, sizeof(visit));
long  num = 0;
for (long  i = 2; i <= n; ++i)
{
if (visit[i] == true)
{
num++;
prime[num] = i;
}
for (long  j = 1; ((j <= num) && (i * prime[j] <= n)); ++j)
{
visit[i * prime[j]] = false;
if (i % prime[j] == 0) break; //点睛之笔
}
}
}
int main()
{
memset(prime, 0, sizeof(prime));
init_prim();
long  i,j;
long  m;
while(scanf("%ld",&m),m)
{
i = j = m;
//printf("%d\n",visit[m]);
while(!visit[i])
i++;
while(!visit[j])
j--;
printf("%ld\n",i - j);
}
return 0;
}

本文出自 “Qero” 博客，请务必保留此出处http://8590696.blog.51cto.com/8580696/1358925

poj3518筛法

原文：http://8590696.blog.51cto.com/8580696/1358925