BOJ)1837 암호제작

문제: icpc.me/1837

P가 너무 크기 때문에 K를 이용하여 답을 구해내야 한다.

우선 K이하의 소수를 에라토스테네스의 체를 이용하여 구해준 뒤

P가 해당 소수들 중 하나라도 나누어 떨어지는 수가 있다면 BAD를 출력하게 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
char a[110];
int k, p[2000000];
bool chk(const char *s, int p) {
    int ret = 0;
    for (int i = 0; s[i]; i++)
        ret = (ret * 10 + s[i] - '0') % p;
    return !ret ? true : false;
}
int main() {
    scanf("%s%d", &a, &k);
    for (int i = 2; i < 2000000; i++) {
        if (p[i])continue;
        for (int j = i + i; j < 2000000; j += i)
            p[j] = true;
    }
    int r = 0, pp = 987654321;
    for (int i = 2; i <= k; i++) {
        if (p[i])continue;
        if (chk(a, i)) {
            r = 1;
            pp = min(pp, i);
        }
    }
    printf("%s ", r ?  "BAD" : "GOOD");
    if (r)
        printf("%d\n", pp);
    return 0;
}