문제

암호제작

풀이

이문제는 C++ 코드를 참고 하게 되었는데, C++은 int형에 ifinite형을 넣을 수 있었더라. 0x3f3f3f3f 이라는 값을 무한대의 값으로 넣을 수 있다 자바같은 경우에는 무한대 수를 위한 자료형이 따로 있는데.. 역시 C++
일단 배열로 검사할 소수들을 추려주면 연산이 속도가 더 빨라진다. 그래서 다까먹어버린 에라토스테네스의 체가 등장한다

		for (int i = 2; i <= 1000000; i++) {
            if (prime[i]) continue;
            for (int j = i + i; j <= 1000000; j += i) {
                prime[j] = true;
            }
        }

그다음에는 이 체에 걸러진 것들로만 검사하면 되는데, 2부터 K까지만 검사해도 된다. 왜냐하면 K값까지 계산했을때 작은 값이라면 BAD이고 검사했는데 검출이 안되면 GOOD이 반환되어야 하기 때문이다.

			for (int j = 0; j < p.length(); j++) {
                m = (m * 10 + p.charAt(j) - '0') % i;
            }
            if (m == 0) {
                r = i;
                break;
            }

전체 코드

전체 코드