bool check() {
    if (bp(g, mod - 1) != 1) {
        return 0;
    }
    for (int i = 1; i * i <= (mod - 1); i++) {
        if ((mod - 1) % i == 0) {
            if (bp(g, i) == 1) {
                return 0;
            }
        }
    }
    return 1;
}