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 |
Re:hhh重新写了一遍过了...确实理清了不少思路In Reply To:很多数据都测试过了成功了,句子也确定没有错但还是WA...不知道什么情况 Posted by:sailist at 2019-03-19 21:17:50 #include <stdio.h> #include <cstring> #include <iostream> using namespace std; #define small 50000 #define prime 0 #define notPrime 1 int offset_numbers[2000001]; bool sqrt_b[small]; #define isPrime(x) x == 0 void iniSmallPrime() { sqrt_b[0] = notPrime; sqrt_b[1] = notPrime; for (int i = 2; i <= small; ++i) { if(sqrt_b[i] == 0) { for (int j = 2*i; j <= small ; j+=i) { sqrt_b[j] = notPrime; } } } } void solveBigPrime(int l,int r) { for (unsigned int i = 2; i*i <= r ; ++i) { if(isPrime(sqrt_b[i])) { int start = l%i == 0? l:l-l%i+i; if(start == i) { start += i; } for (int j = start; j <= r & j>=l ; j+=i) { offset_numbers[j-l] = notPrime; } } } if(l == 1) { offset_numbers[0] = notPrime; } } int main() { memset(sqrt_b,prime, sizeof(sqrt_b)); iniSmallPrime(); int l,r; while(~scanf("%d %d",&l,&r)) { memset(offset_numbers,prime, sizeof(offset_numbers)); solveBigPrime(l,r); int minL=0,minR=0,maxL=0,maxR=0; int minD = 1000000,maxD = 0; int start = 0; bool have = false; while(start <= r-l-1) { if(isPrime(offset_numbers[start]) && start<= r-l-1) { int i = start+1; while (!isPrime(offset_numbers[i]) && i<=r-l) { i++; } if(i>r-l) { break; } if(minD > i-start) { minD = i-start; minL = start+l; minR = i+l; } if(maxD < i-start) { maxD = i-start; maxL = start+l; maxR = i+l; } have = true; start = i; } else { start++; } } if(have) { printf("%d,%d are closest, %d,%d are most distant.\n",minL,minR,maxL,maxR); } else { printf("There are no adjacent primes.\n"); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator