[C++] 소인수분해: 두 소수 p, q의 곱 n이 주어질 때, p, q 알아내기
이 사람은 왜 이런 짓을 했는가? 시험 기간인데 시험 공부는 하기 싫어서 간단한 알고리즘을 짜봤다. 문제 RSA 알고리즘을 배울 때 꼭 한 번씩 들어보는 말. 두 소수 p, q가 주어졌을 때 n을 계산하는 건 매우 단순한 일이지만, 두 소수의 곱 n이 주어졌을 때 p, q를 알아내는 건 NP 문제다. 그래서 어떻게 하면 n이 주어졌을 때 p, q를 빠르게 알아낼 수 있을까?라는 질문이 샤워 도중 떠올랐고, 샤워하면서 한 생각을 코드로 옮겨봤다. 알고리즘 거창한 문제에 비해 내 생각은 단순했다. twosum 문제를 좀 응용하면 되지 않을까? 정확한 사고 과정은 아래와 같았다. 두 소수 p, q를 곱한 n이 있다면, p와 q는 sqrt(n)에서 비슷하게 떨어져 있지 않을까? 3 * 13, 7 * 13을 해봄..
