The Embarraseed Cryptographer

#include <bitset>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

#define long long long int

const int MAX = 1e6 + 5;

int mod(string &n, int p) {
    int ans = 0LL;
    for (int i = 0, size = n.size(); i < size; i++)
        ans = (ans * 10 + n[i] - '0') % p;

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    bitset<MAX> is_prime;
    is_prime.set();

    vector<int> primes(1, 2);
    for (int i = 3; i < MAX; i += 2) {
        if (is_prime[i]) primes.push_back(i);
        for (int j = 1; j < (int) primes.size() && i * primes[j] < MAX; j++) {
            is_prime[i * primes[j]] = false;
            if (!(i % primes[j])) break;
        }
    }

    string K; int L;
    while (cin >> K >> L, K != "0" || L) {
        int prime = -1;
        for (int j = 0; j < (int) primes.size() && primes[j] < L && prime == -1; j++)
            if (!mod(K, primes[j])) prime = primes[j];

        if (prime == -1) cout << "GOOD\n";
        else cout << "BAD " << prime << "\n";
    }
}