(C++) - 백준(BOJ) 1837번 : 암호제작

https://www.acmicpc.net/problem/1837

1837번: 암호제작

큰 수와 소수를 다루는 문제였습니다.

 

 

풀이방법

 1. 2 ~ 100만까지의 소수를 prime배열 변수에 저장합니다.

 

 2. 2 ~ k까지의 소수들 중 하나를 골라 p의 약수인지를 확인합니다. 입력받은 p의 경우에는 수의 범위를 초과하므로 string으로 입력받습니다. p의 첫번째 자리부터 하나씩 자리수를 붙여가며 확인합니다. 해당 수가 i에 나누어 떨어지는지 확인합니다.

 

 3. 모든 자리수에 대해 자리수를 한 개씩 붙여가며 나눠봤을 때 나머지가 0이라면 해당 수는 p의 약수입니다.  찾자마자 루프를 탈출한다면 이것이 p의 약수의 최소값입니다.

 

 4. p의 약수의 최솟값이 k보다 작다면 BAD 아니라면 GOOD입니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
string p;
int k, prime[1000001];

void makePrime(){
    for(int i = 2; i*i <= 1000000; i++){
        if(prime[i]) continue;
        for(int j = i + i; j <= 1000000; j+=i) prime[j] = 1;
    }
}

int main(){
    cin >> p >> k;
    makePrime();
    int ans = 0x3f3f3f3f;
    for(int i = 2; i <= k; i++){
        int ret = 0;
        if(prime[i]) continue;
        for(int j = 0; j < p.size(); j++)
            ret = (ret * 10 + p[j] - '0') % i;
        if(!ret) { ans = i; break;}
    }
    if(ans < k) cout << "BAD" << ' ' << ans;
    else cout << "GOOD";
}