Project Euler Problem 51

問題概要

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

解法

0から9までの数値と'*'のみを用いて文字列を生成し，それの'*'を置き替えた時の素数の個数をチェックしていく．

• '*'が含まれているかどうか
• 最後の桁が奇数かどうか

で若干の枝刈りをするだけで一分に収まった．
素数判定にミラーラビン素数判定法を用いているが，篩を用いて全生成してから調べた方が早かったかもしれない．

実装(Visual Basic.NET)

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 Mod_Pow(ByVal a As Long, ByVal n As Long, ByVal M As Long) As Long
        If n = 0 Then Return 1 Mod M
        Dim Res As Long = Mod_Pow((a * a) Mod M, Int(n / 2), M)
        If n And 1 Then Res = (Res * a) Mod M
        Return Res
    End Function
    Public Shared Function Miller_Rabin(ByVal n As Long) As Boolean
        If n = 2 Then Return True
        If (n Mod 2) = 0 Or n <= 1 Then Return False

        Dim i As Integer = 0, a As Integer() = New Integer() {2, 7, 61, -1}, r As Integer, s As Long = 0, d As Long, x As Long
        d = n - 1
        Do While (d Mod 2) = 0
            s += 1 : d >>= 1
        Loop
        Do While a(i) <> -1 And a(i) < n
            x = Mod_Pow(a(i), d, n)
            If x <> 1 Then
                For r = 0 To s - 1
                    If x = n - 1 Then Exit For
                    x = (x * x) Mod n
                Next
                If r = s Then Return False
            End If
            i += 1
        Loop
        Return True
    End Function
End Class

Module Module1
    '*を数値に置き替えたときに何個素数が出来るか
    Public Function Check(ByVal Value As String) As Integer
        Check = 0
        For i As Integer = 0 To 9
            Check = Check - Algorithm.Miller_Rabin(Long.Parse(Value.Replace("*", i.ToString)))
        Next
    End Function
    Public Target As String
    Public L As Integer
    Public Answer As String
    'Nは1からLの数値
    Public Sub Solve(ByVal N As Integer)
        If N = L Then
            If Target.Contains("*"c) = False Then Return
            For i As Integer = 1 To 9 Step 2
                If i = 5 Then Continue For

                Mid(Target, N, 1) = i.ToString
                Solve(N + 1)
            Next
        ElseIf N = L + 1 Then
            If Check(Target) = 8 Then
                Console.WriteLine("{0}:{1}", Target, Check(Target))
                For i As Integer = 0 To 9
                    If Answer = "" Then
                        If Algorithm.Miller_Rabin(Long.Parse(Target.Replace("*", i.ToString))) Then
                            Answer = Target.Replace("*", i.ToString)
                        End If
                    End If
                Next
            End If
        Else
            For i As Integer = 0 To 9
                If N = 1 And i = 0 Then Continue For
                Mid(Target, N, 1) = i.ToString
                Solve(N + 1)
            Next
            Mid(Target, N, 1) = "*"
            Solve(N + 1)
        End If
    End Sub
    Sub Main()
        Dim TimeCounter As New Stopwatch
        TimeCounter.Start()

        Answer = ""
        For i As Integer = 1 To 19
            L = i
            Target = New String(" ", L)
            Solve(1)
            If Answer <> "" Then Exit For
        Next
        L = 6

        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