UVA 10140 Prime Distance

math uva

我一開始的想法是先把范圍中的質數先找出來. 可是因為范圍 (2, 147, 483, 647) 太大, 所以先找 0 - sqrt(range) 中的質數. (如果 n 不是質數, 那他的其中一個因數會在 sqrt(n) 當中). 輸入test case 後再找那范圍中的質數. 最後用 lower_bound 和 upper_bound 解決

uva10040.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const long long MAXN = 47000;
vector<int> all_primes;
vector<int> primes;
bool isprime[MAXN];

void slave_primes() {
    memset(isprime, true, sizeof(isprime));
    isprime[0] = isprime[1] = false;

    for (int i = 4; i < MAXN; i+=2) {
        isprime[i] = false;
    }
    int limit = sqrt(MAXN) + 1;
    for (int i = 3; i <= limit; i+=2) {
        if (isprime[i]) {
            int count = (MAXN-1) / i;
            int product = count * i;
            for ( ; count >= i; --count, product-=i ) {
                if (isprime[count])
                    isprime[product] = false;
            }
        }
    }

    all_primes.push_back(2);
    for (int i = 3; i < MAXN; i+=2) {
        if (isprime[i]) {
            all_primes.push_back(i);
        }
    }
}

bool is_prime(int value) {
    if(value < MAXN) {
        return isprime[value];
    }
    for(int i = 0; i < all_primes.size() && all_primes[i] < value; ++i) {
        if(value % all_primes[i] == 0) return false;
    }
    return true;
}

void calc(int from, int to) {
    primes.clear();
    for (long long i = from; i <= to; i++) {
        if (is_prime(i)) {
            primes.push_back(i);
        }
    }
}

int main() {
    int from, to;
    slave_primes();

    while (scanf("%d%d", &from, &to) != EOF) {
        calc(from, to);

        if (primes.size() <= 1) {
            printf("There are no adjacent primes.\n");
            continue;
        }

        int minV = 1e9;
        int maxV = 0;
        int minfrom, maxfrom, minto, maxto;

        for (int i = 1; i < primes.size(); ++i) {
            if (primes[i] - primes[i-1] < minV) {
                minV = primes[i] - primes[i-1];
                minfrom = primes[i-1];
                minto = primes[i];
            }
            if (primes[i] - primes[i-1] > maxV) {
                maxV = primes[i] - primes[i-1];
                maxfrom = primes[i-1];
                maxto = primes[i];
            }
        }

        printf("%d,%d are closest, %d,%d are most distant.\n",
            minfrom, minto, maxfrom, maxto);
    }
    return 0;
}