Проверка простых чисел невероятно медленная

Question

У меня есть этот фрагмент кода, который проверяет, является ли данное число простым:

If x Mod 2 = 0 Then
    Return False
End If
For i = 3 To x / 2 + 1 Step 2
    If x Mod i = 0 Then
        Return False
    End If
Next
Return True

Я использую его только для чисел 1E7 <= x <= 2E7.Тем не менее, это очень медленно - я с трудом могу проверить 300 номеров в секунду, поэтому проверка всех x займет более 23 дней ...

Может кто-нибудь дать некоторые советы по улучшению или сказать, что ятак делать излишне?

Answer 1

Это общий алгоритм проверки простого числа.Если вы хотите проверить простое число в массовом порядке, используйте алгоритм http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 2

Посмотрите на термин «Сито Эратосфена». Это алгоритм на две тысячи лет, который намного лучше вашего. Это часто преподается в школе.

Answer 3

Вы также можете поискать тест на простоту AKS.
Это хороший алгоритм для проверки простоты.

Answer 4

Вы обязательно должны изменить свой алгоритм!Вы можете попробовать Сито Эратосфена или более продвинутый Тест на первичность Ферма Помните, что ваш код будет более сложным, так как вам потребуется реализовать модульную арифметику.Посмотрите здесь для списка некоторых еще более математически продвинутых методов.

Answer 5

Используйте Сито Эратосфена , чтобы создать Set, который содержит все простые числа, вплоть до наибольшего числа, которое необходимо проверить. Настройка Set займет некоторое время, но затем проверка, существует ли в нем число, будет очень быстрой.

Answer 6

Поскольку x/2 + 1 является константой в циклической операции, сохраните ее в отдельной переменной перед циклом For.Таким образом, при каждом цикле сохраняется операция деление и сложение .Хотя это может немного увеличить производительность.

Answer 7

это медленно, потому что вы используете х / 2.Я немного изменил твой код.(Я не знаю о синтаксисе VB, возможно, вам придется изменить мой синтаксис.)

If x < 2 Then
    Return False
IF x == 2 Then
    Return True
If x Mod 2 = 0 Then
    Return False
End If
For i = 3 To (i*i)<=x Step 2
    If x Mod i = 0 Then
        Return False
    End If
Next
Return True

Answer 8

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

Пожалуйста, проверьте следующий фрагмент:

 Sub Main()

        Dim primes As New List(Of Integer)
        primes.Add(1)

        For x As Integer = 1 To 1000
            If IsPrime(x, primes) Then
                primes.Add(x)
                Console.WriteLine(x)
            End If
        Next

    End Sub

    Private Function IsPrime(x As Integer, primes As IEnumerable(Of Integer)) As Boolean
        For Each prime In primes
            If prime <> 1 AndAlso prime <> x Then
                If x Mod prime = 0 Then
                    Return False
                End If
            End If
        Next
        Return True
    End Function

Answer 9

Разделите диапазон на несколько кусков и выполните проверки в двух или более потоках, если у вас многоядерный процессор. Или используйте Parallel.For.