Как я могу проверить на первичность?

Question

Я пишу небольшую библиотеку с некоторыми методами, связанными с простыми числами. Поскольку я сделал основы (или рабочие методы) и теперь я ищу некоторую оптимизацию. Конечно, Интернет является отличным местом для этого. Я, однако, наткнулся на проблему округления, и мне было интересно, как ее решить.

В цикле, который я использую, чтобы проверить число на предмет его простоты, более эффективно искать до sqrt (n) вместо n / 2 или даже n - 1. Но из-за проблем с округлением некоторые числа пропускаются, и поэтому некоторые простые числа пропущено! Например, 10000-е простое число должно быть: 104729, но «оптимизированная» версия заканчивается: 103811.

Некоторый код (я знаю, он открыт для дополнительной оптимизации, но я могу обрабатывать только одну вещь за раз):

/// <summary>
/// Method for testing the primality of a number e.g.: return IsPrime(29);
/// History:
/// 1. Initial version, most basic form of testing: m smaller then n -1
/// 2. Implemented m smaller then sqrt(n), optimization due to prime factoring
/// </summary>
/// <param name="test">Number to be tested on primality</param>
/// <returns>True if the number is prime, false otherwise</returns>
public static bool IsPrime(int test)
{
    // 0 and 1 are not prime numbers
    if (test == 0 || test == 1) return false;

    // 2 and 3 are prime numbers
    if (test == 2) return true;

    // all even numbers, save 2, are not prime
    if (test % 2 == 0) return false;

    double squared = Math.Sqrt(test);
    int flooredAndSquared = Convert.ToInt32(Math.Floor(squared));

    // start with 5, make increments of 2, even numbers do not need to be tested
    for (int idx = 3; idx < flooredAndSquared; idx++)
    {
        if (test % idx == 0)
        {
            return false;
        }
    }
    return true;
}

Я знаю, что квадратная часть меня не устраивает (или я провалю), пробовал и Math.Ceiling, примерно с такими же результатами.

Answer 1

Это работает очень быстро для тестирования простых чисел (vb.net)

Dim rnd As New Random()
Const one = 1UL

    Function IsPrime(ByVal n As ULong) As Boolean
        If n Mod 3 = 0 OrElse n Mod 5 = 0 OrElse n Mod 7 = 0 OrElse n Mod 11 = 0 OrElse n Mod 13 = 0 OrElse n Mod 17 = 0 OrElse n Mod 19 = 0 OrElse n Mod 23 = 0 Then
           return false
        End If

        Dim s = n - one

        While s Mod 2 = 0
            s >>= one
        End While

        For i = 0 To 10 - 1
            Dim a = CULng(rnd.NextDouble * n + 1)
            Dim temp = s
            Dim m = Numerics.BigInteger.ModPow(a, s, n)

            While temp <> n - one AndAlso m <> one AndAlso m <> n - one
                m = (m * m) Mod n
                temp = temp * 2UL
            End While

            If m <> n - one AndAlso temp Mod 2 = 0 Then
                Return False
            End If
        Next i

        Return True
    End Function

Answer 2

Я подумал Тестирование простых чисел и простоты было полезно, и алгоритм AKS звучит интересно, даже если он не особенно практичен по сравнению с вероятностными тестами.

Answer 3

private static bool IsPrime(int number) {
    if (number <= 3)
        return true;
    if ((number & 1) == 0)
        return false;
    int x = (int)Math.Sqrt(number) + 1;
    for (int i = 3; i < x; i += 2) {
        if ((number % i) == 0)
            return false;
    }
    return true;
}

Я не могу получить это быстрее ...

Answer 4

Ваш цикл for должен выглядеть следующим образом:

for (int idx = 3; idx * idx <= test; idx++) { ... }

Таким образом, вы избегаете вычислений с плавающей точкой. Должен бежать быстрее и будет точнее. Вот почему условный оператор for является просто логическим выражением: он делает такие вещи возможными.

Answer 5

Попробуйте сито с эратосфенами - которое должно устранить проблемы с корнем и числами с плавающей запятой.

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