QDU-GZS与素数大法(素数筛法)

Description

自从GZS成为G神之后，追随者不计其数，更是有了大名鼎鼎的拜神论：

"吾尝终日编程也，不如须臾之拜拜G神也；吾尝打字刷题也，不如一日三拜G神也；

拜拜G神，程序非长也，而出结果；三拜G神，打字非快也，而能AC。

吾日三拜G神也！！！“

作为菜鸟，经常遇到一些难题，于是就去拜见G神了。G神一看题目，微微一笑说道：“这种水题也算难题？我闭着眼都能一分钟刷十道！”毕竟是G神，我等菜鸟还是得虚心向G神学习。各位大神们，相信这道水题你们也能很快就AC吧。题目是这样的：

给定一个范围[l,r]，求[l, r]中的距离最近的两个相邻素数和距离最远的两个相邻素数。

Input

多组测试数据，每组数据一行，包含两个数字l和r。1<=l<=r<=5*10^6。

Output

如果存在，则按样例格式输出最近的两个素数和最远的两个素数（如果有多个，输出最小的）；如果不存在，输出一行：There are no adjacent primes.

Sample Input 1

2 17

14 17

Sample Output 1

2,3 are closest, 7,11 are most distant.

There are no adjacent primes.

Source

qduoj 第一次月赛 for 2014级

思路：用欧拉筛法先筛出素数，然后遍历两次找出最大的和最小的，注意1既不是素数也不是合数

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<cmath>

using namespace std;

int prime[5000005];

bool vis[5000006];

void oula() {

	int cnt=0;

	memset(prime,0,sizeof(prime));

	memset(vis,false,sizeof(vis));

	for(int t=2; t<=5000005; t++) {

		if(!vis[t])

			prime[cnt++]=t;

		for(int j=0; j<cnt&&t*prime[j]<=5000005; j++) {

			vis[t*prime[j]]=true;

			if(t%prime[j]==0)

				break;

		}

	}

}

int a[5000005];

int b[5000005];

int main()

{

	int l,r;

	int k;

	int k2;

	oula();

	vis[1]=true;

	while(cin>>l>>r)

	{

		k=0;

		k2=0;

		for(int t=l;t<=r;t++)

		{

			if(vis[t]==false)

		    {

			a[k++]=t;

		    }

	    }

	    for(int t=1;t<k;t++)

	    {

	         b[k2++]=a[t]-a[t-1];

		}

		sort(b,b+k2);

		int s1,s2,s3,s4;

		for(int t=1;t<k;t++)

		{

			if(a[t]-a[t-1]==b[0])

			{

				s1=a[t-1];

				s2=a[t];

				break;

			}

		}

		for(int t=1;t<k;t++)

		{

			if(a[t]-a[t-1]==b[k2-1])

			{

				s3=a[t-1];

				s4=a[t];

				break;

			}

		}

		if(k>1)

		cout<<s1<<","<<s2<<" are closest, "<<s3<<","<<s4<<" are most distant."<<endl;

		else

		{

			cout<<"There are no adjacent primes."<<endl;

		}

	}

	return 0;

 }

巴特西

QDU-GZS与素数大法(素数筛法)

最新文章

热门文章