Project Euler Problem 95

問題概要

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2095
を参照

解法

ある数Nの全ての約数はO(√N)で求めることが出来るので，真の約数の和も同じ時間で計算出来る．
よってこれを1000000までの全ての数に行なう．
次にループの確認は今までにアクセスしたものの集合に含まれるものがあるまで，次の数に進み，最終的に元の数に戻っているかで判定出来る．
これはループ回数がそう大きくならないと予想出来るので計算量的には対したことが無いと思われる．

実装(Visual Basic.NET)

この実装だと自分の環境では15.193secで終了する．約数の和を素因数分解を用いて計算すればもう少し早くなる可能性がある．

Imports System
Imports System.IO
Imports System.Text
Imports System.Collections
Imports System.Collections.Generic
Imports System.Math
Imports System.Diagnostics

Public Class Algorithm
    Public Shared Function Divisor(ByVal N As Integer) As Generic.List(Of Integer)
        Dim M As Integer = Int(Math.Sqrt(N))
        Divisor = New Generic.List(Of Integer)
        For i As Integer = 1 To M
            If (N Mod i) = 0 Then
                Divisor.Add(I)
                If i * i <> N Then Divisor.Add(N / I)
            End If
        Next i
    End Function
    Public Shared Function Divisor_SUM(ByVal N As Integer) As Integer
        Divisor_SUM = -N
        Dim t As Generic.List(Of Integer) = Divisor(N)
        For Each i As Integer In t
            Divisor_SUM += i
        Next
    End Function
End Class

Module Module1
    Public Answer As String
    Public Next_Value(1000000) As Integer
    Public Ac(1000000) As Integer
    Public Function Solve(ByVal T As Integer) As Integer
        Solve = 1
        Dim V As Integer = T
        Dim AC As New HashSet(Of Integer)
        While (1)
            AC.Add(V)
            Solve += 1
            V = Next_Value(V)
            If V >= 1000000 Then Return -1
            If AC.Contains(V) And V = T Then
                Exit Function
            ElseIf AC.Contains(V) Then
                Return -1
            End If
        End While
    End Function
    Sub Main()
        Dim TimeCounter As New Stopwatch
        TimeCounter.Start()
        Answer = ""

        For i = 0 To 1000000
            Next_Value(i) = Algorithm.Divisor_SUM(i)
            Ac(i) = 0
        Next
        Dim Ans As Integer = 0
        Dim AVal As Integer = 0
        For i = 0 To 1000000
            If Ans < Solve(i) Then
                Ans = Solve(i)
                AVal = i
                Console.WriteLine("Length:{0} Minval:{1}", Ans, AVal)
            End If
        Next
        TimeCounter.Stop()


        Console.WriteLine("----")
        Console.WriteLine("Answer:{0}", Answer)
        Debug.WriteLine("Answer:{0}", Answer)
        Console.WriteLine("Calculate Time:{0}sec", TimeCounter.ElapsedMilliseconds / 1000)

        '-----
        Console.WriteLine()
        Console.WriteLine("Press Any Key.")
        Console.ReadKey()
    End Sub
End Module