1837번: 암호제작

1837번: 암호제작 - 문자열의 나머지 구하기

P와 K를 입력받아 P라는 숫자가 소수 p,q의 곱으로 나타내질 때,

p와 q 중 하나라도 K보다 작은 p, q가 있을 경우 BAD와 두 소수 중 작은 소수를 출력하고

없을 경우 GOOD을 출력하면 되는 문제이다.

간단하게 생각해보면 K범위가 10^6까지 이므로 10^6까지의 모든 소수를 에라토스테네스 체를 이용하여 구한 뒤

P라는 수에 그 소수들을 하나하나 나누어 본 뒤 하나라도 나누어진다면 BAD,

안나누어진다면 GOOD을 출력하면 되는 간단한 문제이다.

이 때 문제가 되는 부분은 P의 범위가 10^100으로 int, long long 자료형으로는 받을 수 없기에

이를 문자열을 사용해서 받아야한다.

이 때 문자열을 정수로 나눈 나머지를 나머지 연산을 이용하여

ret를 나머지값이라 할 때 문자열 P를 일의 자리부터 보며

ret = (ret * 10 + (P[i] - '0')) % K

를 진행해주면 나머지 값을 구할 수 있다.

이제 ret값이 0일 경우 나누어지는 것이며 문제를 쉽게 풀 수 있다.