[백준] 1837 암호제작

삼성SDS 알고리즘 문제집에 있길래 풀어봤따

소수 2개의 곱 p를주고 , p를 만드는 소수 a,b중 하나라도 k보다 작으면 

BAD 아니면 GOOD을 출력한다

p는 넘넘크다 그래서 k까지 소수구하고 나눠보면 된다 ㅎㅎ

p는 크니까 string으로 받아야한다..!

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
const int MAXN = 1e6 + 3;
bool check[MAXN];
vector<int> prime;
string s;
int k;
bool go(int x) {
    int ret = 0;
    for (int i = 0; s[i]; i++) {
        ret *= 10;
        ret += (s[i] - '0');
        ret %= x;
    }
    return ret == 0;
}
int main() {
    for (int i = 2; i < MAXN; i++) {
        if (!check[i]) {
            prime.push_back(i);
            for (int j = i*2; j < MAXN; j += i) check[j] = true;
        }
    }
    cin >> s >> k;
    for (int i = 0; i < prime.size(); i++) {
        if (prime[i] >= k) break;
        if (go(prime[i])) {
            printf("BAD %d\n", prime[i]); return 0;
        }
    }
    puts("GOOD");
}