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

试过论坛里所有数据可过,依然WA,求BT数据,求助。

Posted by gh2005 at 2011-03-20 11:54:21 on Problem 2689
//Prime Distance.
#include<iostream>
#include<memory>
#include<cmath>
using namespace std;
unsigned int main()
{
	bool isPrime[46342];
	memset(isPrime,true,sizeof(isPrime));
	isPrime[0]=false;isPrime[1]=false;
	for(unsigned int base=2;base<=216;base++)
		for(unsigned int fac=2;fac*base<46342;fac++)
			isPrime[fac*base]=false;
	unsigned int	l=0,u=0;
	cin >> l >> u;
	while(cin)
	{
		bool yesAdj=false;
		unsigned int	evenCount=0;
		unsigned int	min=10000000,max=0;
		unsigned int	cloMin=0,cloMax=0,disMin=0,disMax=0;
		bool* isPri=new bool[u-l+1];
		for(unsigned int i=0;i<u-l+1;i++) isPri[i]=true;
		for(unsigned int i=2;i<46342;i++)
		{
			if(i>u) break;
			if(isPrime[i])
			{
				unsigned int	redyFi=l/i;						//number ready to be the first length
				if(redyFi>1 && redyFi*i==l) 
				{
					if(isPri[0]) evenCount++;
					isPri[0]=false;					//if redyFi*i==l,then the first number is prime
				}
				if(redyFi<2)	redyFi=2;
				else			redyFi++;
				while(redyFi*i<=u)					//every even number of redyFi that more than l
				{
					if(isPri[redyFi*i-l]) evenCount++;
					isPri[redyFi*i-l]=false;
					redyFi++;
				}
			}
		}
		if(l==1)
		{
			evenCount++;
			isPri[0]=false;
		}
		if(evenCount<=u-l+1-2 && u-l+1-2>0)
		{
			unsigned int prev=0;
			unsigned int saveI=0;
			yesAdj=true;
			for(unsigned int i=0;i<u-l+1;i++)
			{
				if(isPri[i])
				{
					prev=l+i;
					saveI=i+1;
					break;
				}
			}
			for(unsigned int i=saveI;i<u-l+1;i++)
			{
				if(isPri[i])
				{
					if(l+i-prev > max)
					{
						max=l+i-prev;
						disMin=prev;
						disMax=l+i;
					}
					if(l+i-prev < min)
					{
						min=l+i-prev;
						cloMin=prev;
						cloMax=l+i;
					}
					prev=l+i;
				}
			}
		}
		if(yesAdj)	cout << cloMin << ',' << cloMax << " are closest, " << disMin << ',' << disMax << " are most distant.\n";
		else			cout << "There are no adjacent primes.\n";
		delete[]	isPri;
		cin >> l >> u;
	}
	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