Генерация Простых Чисел N


Я пытаюсь создать П чисел, где мой Н = 200,000.

Метод, который я думаю, я написал -

  1. Начнем с первого премьер 2
  2. Инкремент можно простое число по 1
  3. Ли премьер-делится на найденные премьер (если да выход на 2)
  4. Остановите испытание, когда рядом нашли премьер-это больше, чем половина возможного премьер (выход на 2)
  5. Добавить его в список

Это работает, но это занимает 1 минуту 8 секунд который, кажется, очень долго. Это мой алгоритм не делает то, что я думаю или это просто неправильно реализовано? Или я не должен использовать эти массивы?

Option Explicit On
Option Strict On
Option Infer On
Option Compare Text
Module PrimeNumberGenerator
     Sub Main()
        Static start_time As DateTime
        Static end_time As DateTime
        Dim elapsed_time As TimeSpan
        start_time = DateTime.Now
        Dim targetPrimes(199999) As Integer
        targetPrimes = GetPrimes(targetPrimes.Length)
        end_time = DateTime.Now
        elapsed_time = end_time - start_time
        Debug.Print(elapsed_time.ToString)
        Debug.Print((targetPrimes(500)).ToString)
    End Sub

    Private Function GetPrimes(ByVal countOfPrimes As Integer) As Integer()
        Dim myPrimes(countOfPrimes - 1) As Integer
        Dim primeIndex As Integer = 0
        Dim testIndex As Integer = 0
        Dim possiblePrime As Integer = 2
        myPrimes(primeIndex) = possiblePrime
        Do Until primeIndex = countOfPrimes - 1
            possiblePrime += 1
            For testIndex = 0 To primeIndex
                If possiblePrime Mod myPrimes(testIndex) = 0 Then
                    Continue Do
                ElseIf myPrimes(testIndex + 1) * 2 > possiblePrime Then
                    Exit For
                End If
            Next
            primeIndex += 1
            myPrimes(primeIndex) = possiblePrime
        Loop
        Return myPrimes
    End Function
End Module


148
2
задан 7 марта 2018 в 12:03 Источник Поделиться
Комментарии
4 ответа

Одна скорость твик для поиска только квадратный корень 'possiblePrime'. Это позволит сократить вычисления значительный порядок.

Еще одно изменение заключается в добавлении 2, а не 1 к 'possiblePrime' как вы знаете, что все четные числа > 2 не являются первичными.

2
ответ дан 7 марта 2018 в 05:03 Источник Поделиться

Я предпочитаю элегантные петель - код, который не имеет явных или скрытых перерывов. Не всегда легко добиться, и бывают случаи, когда это кажется невозможным. Я тоже предпочитаю позитивные циклы, где продолжение основывается на положительной прямое указание, а не отрицательный или сочетание негативных высказываний. Иногда эта льгота может быть удовлетворяется через небольшой твик переменной.

Я смотрю на внутренний For петли, она имеет два перерыва в непрерывности (Continue Do и Exit For).


    Do Until primeIndex = countOfPrimes - 1
possiblePrime += 1
For testIndex = 0 To primeIndex
If possiblePrime Mod myPrimes(testIndex) = 0 Then
Continue Do
ElseIf myPrimes(testIndex + 1) * 2 > possiblePrime Then
Exit For
End If
Next
primeIndex += 1
myPrimes(primeIndex) = possiblePrime
Loop

Что также может быть достигнуто путем:

    Dim continueLooking as Boolean, primeFound as Boolean ' loop management
Do Until primeIndex = countOfPrimes - 1
possiblePrime += 1
testIndex = 0
continueLooking = True
primeFound = True ' seems counterintuitive to start off at True!
While continueLooking
'First check
If possiblePrime Mod myPrimes(testIndex) = 0 Then
continueLooking = False
primeFound = False
Else
'Second check
continueLooking = (Math.Pow(myPrimes(testIndex + 1),2) > possiblePrime)
End If
End While 'Wend
If primeFound then
primeIndex += 1
myPrimes(primeIndex) = possiblePrime
End If
Loop

Очевидно, некоторые больше внутреннего управления была использована для достижения элегантности, компромисс всегда существует.

1
ответ дан 8 марта 2018 в 02:03 Источник Поделиться

Если скорость имеет большое значение, вы можете использовать генератор случайных чисел с последующим делением теста, обычно это быстрее для больших чисел, но если вы останетесь ограничено 32 битами, я не уверен, если это будет быстрее.

0
ответ дан 7 марта 2018 в 09:03 Источник Поделиться

Только выполнение рекомендаций документальные правовые акты (в сравнение квадратного корня из значения критерия, добавить 2 каждый раз). Это должно быть значительно быстрее.

Private Function GetPrimes(ByVal countOfPrimes As Integer) As Integer()
Dim myPrimes(countOfPrimes - 1) As Integer
Dim primeIndex As Integer = 0
Dim testIndex As Integer = 0
Dim possiblePrime As Integer = 1
myPrimes(0) = 2
Do Until primeIndex = countOfPrimes - 1
possiblePrime += 2
For testIndex = 0 To primeIndex
If possiblePrime Mod myPrimes(testIndex) = 0 Then
Continue Do
ElseIf myPrimes(testIndex) >= Math.Sqrt(possiblePrime) Then
Exit For
End If
Next
primeIndex += 1
myPrimes(primeIndex) = possiblePrime
Loop
Return myPrimes
End Function

0
ответ дан 8 марта 2018 в 03:03 Источник Поделиться