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