Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

线形筛+普通筛

Posted by ACAccepted at 2019-01-21 10:22:37 on Problem 2689 and last updated at 2019-01-21 10:23:08
#include <iostream>
#include <cstring>
#include <cstdio>
#include <bitset>
using namespace std;
const int MAXN=65535;
const int INF=1000050;
long long l,r;
long long a,b,c,d,e,f;
long long prim[MAXN],num;
bitset<INF> v;

void prime()
{
	v.reset();
	for(int i=2;i<=MAXN;i++)
	{
		if(!v[i])prim[++num]=i;
		for(int j=1;j<=num;j++)
		{
			if(i*prim[j]>MAXN)break;
			v[i*prim[j]]=1;
			if(i%prim[j]==0)break;
		}
	}
}//线形筛

void get_prime()
{
	v.set();
	for(long long i=1;i<=num;i++)
		for(long long j=r/prim[i];j>1&&prim[i]*j>=l;j--)v[prim[i]*j-l]=false;
}//普通筛

int main()
{
	prime();
	while(cin>>l>>r)
	{
		if(l==1)l=2;
		get_prime();
		a=-1000000,b=1000000,c=0,d=0,e=0,f=0;
		for(long long i=l;i<=r;i++)
		{
			if(v[i-l])
			{
				e=f;f=i;
				if(e>0)
				{
					if(f-e<b-a)b=f,a=e;
					if(f-e>d-c)d=f,c=e;
				}
			}
		}
		if(a<0)puts("There are no adjacent primes.");
		else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",a,b,c,d);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator