오일러 프로젝트 47

오일러 프로젝트 47번은 서로 겹치지 않는 소인수를 갖는 자연수가 연속해서 네 번 나오는 경우를 찾는 것이다. 이 문제는 크게 어렵지 않아 보인다. 간단히 어떤 자연수 N을 소인수분해하여 소인수가 4가지 나오고, N+1을 소인수분해하여 소인수가 4가지 나왔을 때 두 자연수의 소인수 사이에 겹치는 값이 없어야 한다. 이렇게 4개의 연속한 자연수가 “그 직전” 수와 겹치는 소인수가 없이 4개씩 나오는 경우를 찾는다. 소인수분해만 할 수 있으면 푸는 것 자체는 어렵지 않지만, C로 작성된 코드로도 40~50초가 걸렸다는 사람이 부지기수일 정도로 성능 최적화 측면에서 상당한 난이도를 자랑하는 문제이다. 오일러 프로젝트 47 더보기