有多组数据，每组一个n，若n为0，程序结束。若n为质数，输出0.否则输出离它最近的两个质数（一个比n大，一个比n小）之差。（质数最大为 1299709，即抵十万个素数。）
真的hei水 非常水 超级无敌水 拿来背质数筛 
线性筛法 -- 欧拉筛法
比普通的Eratosthenes筛法（复杂度为(O(nloglogn)）效率要高些 为O(N)
用v数组储存每个数的最小质因子
其他题可能会用到这个：prime[j]必定是prime[j]*i的最小质因子
1 void primes(int n) 2 { 3 memset(v,0,sizeof(v));//最小质因子 4 cnt=0;//质数数量 5 for(int i=2;i<=n;i++) 6 {//给i乘上一个质因子 7 if(!v[i]) v[i]=i,prime[++cnt]=i;//若i为质数 8 for(int j=1;j<=cnt;j++) 9 if(prime[j]>v[i]||prime[j]>(n/i)) break;//i有比prime[j]更小的质因子||超出n的范围 10 else v[i*prime[j]]=prime[j]; 11 } 12 }
本题 就先把素数预先处理出来 如果它的最小质因子为它本身即v[x]==x则 x为素数
如果不是素数 就从左往右扫出第一个大于x的素数prime[i] 然后输出prime[i]-prime[i-1]
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int X=1299709+5; 4 int n,k; 5 int v[X],pri[X],cnt; 6 template<class t>void rd(t &x) 7 { 8 x=0;int w=0;char ch=0; 9 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 10 while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); 11 x=w?-x:x; 12 } 13 14 void prime() 15 { 16 memset(v,0,sizeof(v));//最小质因子 17 memset(pri,0,sizeof(pri)); 18 cnt=0;//质数数量 19 for(int i=2;i<=X;i++) 20 { 21 if(!v[i]) v[i]=i,pri[++cnt]=i; 22 for(int j=1;j<=cnt;j++) 23 if(pri[j]>v[i]||pri[j]>(X/i)) break; 24 else v[i*pri[j]]=pri[j]; 25 } 26 } 27 28 int main() 29 { 30 prime(); 31 while(scanf("%d",&n)&&n) 32 { 33 if(v[n]==n) printf("0 "); 34 else 35 for(int i=2;i<=cnt;i++) 36 if(pri[i]>n) 37 { 38 printf("%d ",pri[i]-pri[i-1]); 39 break; 40 } 41 } 42 return 0; 43 }
感觉比之前做的luogu新手村还简单