| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
试过论坛里所有数据可过,依然WA,求BT数据,求助。//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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator