异想天开

What's the true meaning of light, Could you tell me why

素数距离问题

日期:2015-05-07 16:57:39
  
最后更新日期:2015-05-07 16:57:39
NYOJ
http://acm.nyist.net/JudgeOnline/problem.php?pid=24
描述
现在给出你一些数,要求你写出一个程序,输出这些整数相邻最近的素数,并输出其相距长度。如果左右有等距离长度素数,则输出左侧的值及相应距离。
如果输入的整数本身就是素数,则输出该素数本身,距离输出0
输入
第一行给出测试数据组数N(0接下来的N行每行有一个整数M(0输出
每行输出两个整数 A B.
其中A表示离相应测试数据最近的素数,B表示其间的距离。
样例输入
3
6
8
10
样例输出
5 1
7 1
11 1
解析:
判断素数问题,考察边界1和999999,需要注意的是打表筛选时,999999最近的素数是1000003,所以表的长度需要超过1000000。
[code lang="cpp"]
#include<stdio.h>
#include <string.h>
#define ARRAY_LEN 31251
#define WORD_LEN 32
unsigned int p[ARRAY_LEN];
#define LEN ARRAY_LEN*WORD_LEN
int cal(){
int i=2,j=0,k,m;
memset(p,0xffffffff,sizeof(p));
p[0]=0xfffffffc;
for (i=2;i<LEN;i++){
k=i/WORD_LEN;
m=1<<(i%WORD_LEN);
if (p[k]&m){
for (j=i+i;j<LEN;j+=i){
k=j/WORD_LEN;
m=1<<(j%WORD_LEN);
if (p[k]&m){
p[k]=p[k]&(~m);
}
}
}
}
return 0;
}

int sovle(){
int t=0,n=0, x,y,i,tmp1,tmp2;
cal();

scanf("%d",&t);
while(t--){
tmp1=0;
tmp2=0;
scanf("%d",&n);
x=n/WORD_LEN;
y=1<<(n%WORD_LEN);
if (p[x]&y){
printf("%d 0\n",n);
continue;
}

for (i=n;i<LEN;i++){
x=i/WORD_LEN;
y=1<<(i%WORD_LEN);
if (p[x]&y){
tmp1=i;
break;
}
}

for (i=n;i>=2;i--){
x=i/WORD_LEN;
y=1<<(i%WORD_LEN);
if (p[x]&y){
tmp2=i;
break;
}
}

if ((tmp1 && tmp2 && ((n-tmp2)>(tmp1-n))) || (!tmp2)) {
printf("%d %d\n",tmp1,tmp1-n);
} else {
printf("%d %d\n",tmp2,n-tmp2);
}

}
return 0;
}

int main()
{
sovle();
return 0;
}
[/code]