Project Euler Problem 211

Problem 211

04 October 2008

For a positive integer n, let σ₂(n) be the sum of the squares of its divisors. For example,

σ₂(10) = 1 + 4 + 25 + 100 = 130.

Find the sum of all n, 0 n 64,000,000 such that σ₂(n) is a perfect square.

 

Solution in C#

Brute force took several hours.

 

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Euler {
    static class Program {
        static void Main(string[] args) {
            long sum = 0;
            for (long n = 1; n < 64000000; n++) {
                long divisor2sum = 1;
                for (long i = 2; i * i <= n; i++) {
                    if (n % i == 0) {
                        divisor2sum += i * i;
                        if (i * i != n) {
                            long i2 = n / i;
                            divisor2sum += i2 * i2;
                        }
                    }
                }
                if (n > 1) divisor2sum += n * n;
                double d = Math.Sqrt(divisor2sum);
                if (d == Math.Floor(d)) {
                    sum += n;
                    Console.WriteLine("{0} {1}", n, divisor2sum);
                }
            }
            Console.WriteLine(sum);
            Console.ReadKey();
        }
    }
}