n 值的质数

Question

任务：质数（或质数）是一个大于 1 的自然数，除了 1 和它本身之外没有其他正除数。以下是前几个素数：

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31...

定义一个函数，给定一个整数 n，确定前 n 个素数。

问题：我目前正在获取 0-n 之间的素数，但不是 n 个素数。

我的代码是：

    Sub MACRO()
    Z = InputBox("enter number")
        Dim x As Long, n As Long, i As Long, PrimeNumber As Long
        x = 0
            With ActiveSheet
            For n = 1 To Z
            For i = 2 To n - 1
                    If n Mod i = 0 Then
                        x = 0
                        Exit For
                    Else
                        x = 1
                    End If
                Next
                If x = 1 Then
                    PrimeNumber = PrimeNumber + 1
                .Cells(PrimeNumber, 1) = n
                End If
            Next
        End With
    End Sub

Answer 1

在搜索素数时，您可以通过观察来加快速度：

• 你只需要测试奇数
• 您可以排除可被 2 整除的测试
• 您只需要测试先前找到的素数的可整性
• 你只需要测试到候选数的平方根

像这样的东西

Sub FindPrimes(NumPrimes As Long, Primes() As Long)
    Dim Candidate As Long, Factor As Long
    Dim idxP As Long
    Dim IsPrime As Boolean
    Dim i As Long

    ReDim Primes(1 To NumPrimes)

    Primes(1) = 2
    Primes(2) = 3

    idxP = 3
    Candidate = 3

    Do While idxP <= NumPrimes
        Candidate = Candidate + 2
        i = 2
        IsPrime = True
        Do
            Factor = Candidate \ Primes(i)
            ' Factor < Primes(i) implies Primes(i) > Sqrt(Candidate)
            If Factor < Primes(i) Then
                Exit Do
            End If
            If Factor * Primes(i) = Candidate Then
                IsPrime = False
                Exit Do
            End If
            i = i + 1
        Loop
        If IsPrime Then
            Primes(idxP) = Candidate
            idxP = idxP + 1
        End If
    Loop
End Sub

像这样使用它

Sub Demo()
    Dim Primes() As Long
    Dim Num As Long

    FindPrimes Num, Primes

    ' Primes is now an array of the first Num primes
End Sub

在我的硬件上，这会在 50 毫秒内找到前 10,000 个素数（FWIW，与需要 10 秒的 Foxfire 的答案相比）