1. 풀이방법
- 첫번째는 소수 판별과 두번째는 longlong 범위를 넘어가는 big integer에 대한 mod연산 구현
- 이 두가지를 구현하는 문제 인데 첫번째는 에라토스테네스의 채를 이용하여 소수 set을 만들었고 (k의최대값까지)
- string으로 큰수를 받아서 (10^100 이므로) c++에서 제공하는 정수를 담는 자료형으로는 어림도 없으므로
- 그 문자열로 받은 큰 수를 int로 나누어보는 함수를 구현하였다 (나누는 수는 k보다 작으므로 int 가능)
2. 주의사항
- 제 구현에서는 소수 set을 만드는 부분과 나누어지는지 확인하는 부분이 나누어져있지만
- 짜고 나서 보니 에라토스테네스의 체를 이용하여 구해가면서 그때그때 판별을 하면 연산의 수를 줄일 수 있을
- 것 같습니다.
3. 나의코드
#include<bits/stdc++.h>
using namespace std;
const int maxk= 1e6+1;
bool isitprime[maxk]; //false 이면 소수
string ps;
int k;
int resulti = 0;
void makeprimeset() { //소수 판별
isitprime[0] = true; isitprime[1] = true;
for (int i = 2; i <= k; i++) {
if (isitprime[i] == false) { //소수이면
int index = i;
int tmp = 2;
while (index * tmp <= k) { //배수는 모두 소수가 아님
isitprime[index * tmp] = true;
tmp++;
}
}
}
}
bool bigintdivide(int p) {
int tmpsum = 0;
for (int i = 0; i < ps.length(); i++) {
tmpsum = (tmpsum * 10 + (ps[i] - '0'))%p; //앞자리수 부터
}
if (tmpsum == 0) return true;
else return false;
}
bool isunderk() {
for (int i = 2; i <k; i++) {
if (isitprime[i] == false) {
if (bigintdivide(i)) {
resulti = i; return false;
}
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> ps >> k;
makeprimeset(); //에라토스테네스의 채
if (isunderk()) cout << "GOOD" << "\n";
else cout << "BAD" << " " << resulti << "\n";
return 0;
}
'알고리즘 문제풀이 > 수학' 카테고리의 다른 글
백준 2609 [C++] (0) | 2020.12.03 |
---|