uva 1521 - GCD Guessing Game(貪心)

uva 1521 - GCD Guessing Game(貪心)

題目鏈接：uva 1521 - GCD Guessing Game

題目大意：給定一個數N，現在又一個數x，在1~N之間，現在每次可以猜一個數a，返回gcd(x,a),問說最少猜幾次可以確定x。

解題思路：其實就將1~N裡面的素數都要考慮一遍，因為有一個N的限制，所以每次選出來的素數的積不大於N即可。

#include 
#include 
#include 

using namespace std;
const int maxn = 10000;

int N, v[maxn];
int npri, vis[maxn+5], prime[maxn+5];

void prime_table (int n) {
    npri = 0;
    for (int i = 2; i <= n; i++) {
        if (vis[i])
            continue;

        prime[npri++] = i;
        for (int j = i * i; j <= n; j += i)
            vis[j] = 1;
    }
}

void set (int u, int x) {

    for (int i = x; i >= 0; i--) {
        int k = prime[i];
        if (v[k] || k > u)
            continue;

        v[k] = 1;
        set(u/k, i-1);
        return;
    }
}

int solve () {
    int ans = 0;
    memset(v, 0, sizeof(v));

    for (int i = npri-1; i >= 0; i--) {
        int u = prime[i];

        if (v[u] || u > N)
            continue;

        ans++;
        v[u] = 1;

        set(N/u, i-1);
    }

    return ans;
}

int main () {
    prime_table(maxn);
    while (scanf("%d", &N) == 1) {
        printf("%d\n", solve());
    }
    return 0;
}