Untitled

mail@pastecode.io avatar
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;
}