| ||||||||||
| 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