Project Euler #135: Same differences

  • + 0 comments

    For last 5 test case, common method,to iterate from 1 to sqrt(n) to fetch all divisors, would fail with time out. Thus, we need an efficient way to find all divisors. Here's my method, hope this helps.

    1. calculate all primes less than sqrt(8000000) +1
    2. find all prime divisors and how many times each prime divisor shows up for n.
    3. With the result in step 2, we can find all divisors less than sqrt(n) + 1 for n,
    4. Iterate divisors we got from step 3, calculate how many solutions for n.