q3132_スーパー素数.vb

Public Class Class1

    Public Shared Sub Main()
        Console.WriteLine(q3132(CInt(Console.ReadLine())))
        'For N As Int32 = 1 To 2017
        '   Dim a As Int32 = q3132(N)
        'Next
    End Sub

    Public Shared Function q3132(ByVal N As Int32) As Int32
        ''
        '与数N番目のスーパー素数を得る為に、まず自然数nMaxまでの素数列を求めることにする'
        'ここでnMaxはピエール・デザルトにより'
        '　n 番目の素数を pn とすると、n ≥ 6 に対して'
        '　n(log(n)+log(log(n))-1) < pn < n(log(n)+log(log(n)))'
        'なので、この上限側を与数Nに対して２回計算して利用する'
        ''
        Dim n1 As Int32 = N
        For i As Int32 = 1 To 2
            If n1 < 6 Then n1 = 6
            n1 *= Math.Log(n1) + Math.Log(Math.Log(n1))
        Next
        Dim nMax As Int32 = n1
        ''
        'nMaxまでの素数をエラト(ryで求める'
        ''
        Dim pList As New System.Collections.Generic.List(Of Int32)
        Dim Primes(nMax) As Int32
        For i As Int32 = 2 To nMax
            Primes(i) = i
        Next
        Dim jMax As Int32 = Math.Sqrt(nMax)
        Dim j As Int32 = 1
        Do
            Dim d As Int32
            Do
                j += 1
                d = Primes(j)
            Loop Until d <> 0
            pList.Add(d)
            For k As Int32 = d + d To nMax Step d
                Primes(k) = 0
            Next
        Loop While j < jMax
        For i As Int32 = j + 1 To nMax
            If Primes(i) <> 0 Then
                pList.Add(Primes(i))
            End If
        Next

        'Debug.WriteLine("{0},{1}", nMax, pList.Item(pList.Item(N - 1) - 1))
        Return pList.Item(pList.Item(N - 1) - 1)

    End Function

End Class

エラトステネスのふるい