# Untitled

unknown
plain_text
a year ago
2.0 kB
1
Indexable
Never
```#include <iostream>
#include <vector>
#define bsize 100000//
using namespace std;

bool prime[100000];//容十萬的表格
vector<int> primes;
void findprime(){ //建構質數表
for (int i=0;i<bsize;i++){//
prime[i]=true;
}
prime[0]=false;
prime[1]=false;
for (int i=2; i<bsize; i++){
if (prime[i]){
if((long long)i*i<bsize){//
for(int m=i*i; m<bsize; m+=i)
prime[m] = false;
}
primes.push_back(i);//儲存已知的質數
}
}
}
void cal(long long l, long long u){
bool isComposite[1000001] = {false};
for(int i = 0; i<primes.size() && (long long)primes[i] * primes[i] <= u; ++i){
const int tmp = primes[i]; //利用tmp存取質數
long long st;//在合數表中，欲刪除的起始值
if(l%tmp==0)
st = l;
else
st = l - (l%tmp) + tmp;
for(long long n = st; n<=u; n+=tmp){
if(n!=tmp)
isComposite[n-l] = true;//把合數刪除;題目說U-L不超過10^6
}
}
int MIN=99999999;
int MAX=0;
long long c1, c2, d1, d2;
c1 = 0, c2 = u, d1 = 0, d2 = 0;
int lastPrime = 0;
for(long long n = l; n<=u; n++){
if(!isComposite[n-l]){
if(lastPrime!=0){
if(c2 - c1 > n-lastPrime){
c2 = n;
c1 = lastPrime;
}
if(d2 - d1 < n-lastPrime){
d2 = n;
d1 = lastPrime;
}
}
lastPrime = n;
}
}
if (c1 == 0)
cout << "There are no adjacent primes." << endl;
printf("%lld,%lld are closest, %lld,%lld are most distant.\n", c1, c2, d1, d2);
}

int main()
{
int l,u;
findprime();//建立質數表
while(cin>>l>>u){
cal(l,u);
}
return 0;
}
```