Back to the Problem
Sum divisors in pairs up to √N (excluding N itself) and compare.
Complexity: O(√N) or better