n值的素数 [英] Prime Number for n value

问题描述

任务:素数(或素数)是大于1的自然数，没有正数 除1及其本身以外的除数.以下是前几个素数:

Task: A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. Here are the first few prime numbers:

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

定义一个给定整数n的函数，该函数确定前n个素数 数字.

Define a function that, given an integer n, determines the first n prime numbers.

问题:我目前得到的质数在0-n之间，但不是n个质数.

Problem: I am currently getting the primes between 0-n but not n prime numbers.

我的代码是:

    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

推荐答案

搜索Prime时，通过观察可以加快速度:

When searching for Primes, you speed thing up by observing:

• 您只需要测试奇数
• 您可以按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

在我的硬件上，这会在50ms内找到前10,000个素数(FWIW，而Foxfire的答案是10s)

On my hardware, this finds the first 10,000 primes in 50ms (FWIW, compared to Foxfire's answer which takes 10s)

这篇关于n值的素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！