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

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

Я не знаю, действительно ли это то, что вы ищете, но если вы действительно обеспокоены скоростью, то вам следует использовать вероятностные методы проверки простоты, а не использовать сито. Рабин-Миллер - вероятностный тест на простоту, используемый Mathematica.

Answer 2

Полагаю, это ваша проблема:

for (int idx = 3; idx < flooredAndSquared; idx++)

Это должно быть

for (int idx = 3; idx <= flooredAndSquared; idx++)

так что вы не получите квадратные числа в качестве простых чисел. Также вы можете использовать «idx + = 2» вместо «idx ++», потому что вам нужно только проверять нечетные числа (как вы написали в комментарии выше ...)

Answer 3

К сожалению, я не пробовал алгоритмические подходы раньше. Но если вы хотите эффективно реализовать свой подход, я бы посоветовал заняться кэшированием. Создайте массив для хранения всех простых чисел, меньших заданного порога, заполните этот массив и выполните поиск в нем / используя его.

В следующем примере для определения, является ли число простым, в лучшем случае будет O (1) (а именно, когда число меньше или равно maxPrime, что составляет 821 461 для буфера 64 КБ), и несколько оптимизирован для других случаев (проверяя мод только на 64 000 номеров из первых 820 000 - около 8%).

(Примечание. Не принимайте этот ответ за «оптимальный» подход. Это скорее пример того, как оптимизировать реализацию.)

public static class PrimeChecker
{
    private const int BufferSize = 64 * 1024; // 64K * sizeof(int) == 256 KB

    private static int[] primes;
    public static int MaxPrime { get; private set; }

    public static bool IsPrime(int value)
    {
        if (value <= MaxPrime)
        {
            return Array.BinarySearch(primes, value) >= 0;
        }
        else
        {
            return IsPrime(value, primes.Length) && IsLargerPrime(value);
        }
    }

    static PrimeChecker()
    {
        primes = new int[BufferSize];
        primes[0] = 2;
        for (int i = 1, x = 3; i < primes.Length; x += 2)
        {
            if (IsPrime(x, i))
                primes[i++] = x;
        }
        MaxPrime = primes[primes.Length - 1];
    }

    private static bool IsPrime(int value, int primesLength)
    {
        for (int i = 0; i < primesLength; ++i)
        {
            if (value % primes[i] == 0)
                return false;
        }
        return true;
    }

    private static bool IsLargerPrime(int value)
    {
        int max = (int)Math.Sqrt(value);
        for (int i = MaxPrime + 2; i <= max; i += 2)
        {
            if (value % i == 0)
                return false;
        }
        return true;
    }
}

Answer 4

Я разместил класс, который использует сито или Eratosthenes для вычисления простых чисел здесь:

Ограничен ли размер массива верхним пределом int (2147483647)?

Answer 5

Как сказал Марк, тест Миллера-Рабина на самом деле очень хороший путь. Дополнительная ссылка (с псевдокодом) - статья Википедии об этом.

Следует отметить, что, хотя он является вероятностным, тестируя лишь очень небольшое количество случаев, вы можете определить, является ли число простым для чисел в диапазоне int (и почти длинном). См. эту часть этой статьи Википедии , или ссылку на доказательство первичности для получения более подробной информации.

Я бы также рекомендовал прочитать эту статью о модульном возведении в степень, так как в противном случае вы будете иметь дело с очень очень большими числами при попытке выполнить тест Миллера-Рабина ...

Answer 6

Возможно, вы захотите взглянуть на маленькую теорему Ферма .

Вот псевдокод из книги Алгоритмы С. Дасгупты, С.Х. Пападимитриу и У.В. Вазирани , где n - это число, которое вы проверяете на простоту.

Pick a positive integer a < n at random
if a^n-1 is equivalent to 1 (mod n)
   return yes
else
   return no

Реализация теоремы Ферма должна быть быстрее, чем сито. Однако есть числа Кармайкла, которые проходят тест Ферма и НЕ являются простыми. Есть обходные пути для этого. Я рекомендую обратиться к Раздел 1.3 в вышеупомянутой книге . Это все о тестировании на первичность и может быть полезно для вас.

Answer 7

У меня быстрый алгоритм проверки простых чисел. Вы можете улучшить свой алгоритм, если знаете, что простые числа имеют форму 6k ± 1, за исключением 2 и 3. Итак, сначала вы можете проверить, делится ли ввод на 2 или 3. Затем проверьте все числа в форме 6k. ± 1 ≤ √вход.

bool IsPrime(int input)
        {
            //2 and 3 are primes
            if (input == 2 || input == 3)
                return true; 
            else if (input % 2 == 0 || input % 3 == 0)
                return false;     //Is divisible by 2 or 3?
            else
            {
                for (int i = 5; i * i <= input; i += 6)
                {
                    if (input % i == 0 || input % (i + 2) == 0)
                        return false;
                }
                return true;
            }
        }

Answer 8

Попробуйте это ...

if (testVal == 2) return true;
if (testVal % 2 == 0) return false;

for (int i = 3; i <= Math.Ceiling(Math.Sqrt(testVal)); i += 2)
{
   if (testVal % i == 0)
       return false;
}

return true;

Я использовал это довольно много раз .. Не так быстро, как сито ... но это работает.

Answer 9

Вот наполовину достойная функция, которую я написал для решения одного из Эйлеров:

private static long IsPrime(long input)
{
    if ((input % 2) == 0)
    {
        return 2;
    }
    else if ((input == 1))
    {
        return 1;
    }
    else
    {
        long threshold = (Convert.ToInt64(Math.Sqrt(input)));
        long tryDivide = 3;
        while (tryDivide < threshold)
        {
            if ((input % tryDivide) == 0)
            {
                Console.WriteLine("Found a factor: " + tryDivide);
                return tryDivide;
            }
            tryDivide += 2;
        }
        Console.WriteLine("Found a factor: " + input);
        return -1;
    }
}

Answer 10

В случае, если кто-то еще заинтересован, вот мое преобразование процедуры Мухаммеда выше в VBA. Я добавил проверку, чтобы исключить 1, 0 и отрицательные числа, так как все они определены как не простые.

Я только что проверил это в Excel VBA:

Function IsPrime(input_num As Long) As Boolean
    Dim i As Long
    If input_num < 2 Then '1, 0, and negative numbers are all defined as not prime.
        IsPrime = False: Exit Function
    ElseIf input_num = 2 Then
        IsPrime = True: Exit Function '2 is a prime
    ElseIf input_num = 3 Then
        IsPrime = True: Exit Function '3 is a prime.
    ElseIf input_num Mod 2 = 0 Then
        IsPrime = False: Exit Function 'divisible by 2, so not a prime.
    ElseIf input_num Mod 3 = 0 Then
        IsPrime = False: Exit Function 'divisible by 3, so not a prime.
    Else
        'from here on, we only need to check for factors where
        '6k ± 1 = square root of input_num:
        i = 5
        Do While i * i <= input_num
            If input_num Mod i = 0 Then
                IsPrime = False: Exit Function
            ElseIf input_num Mod (i + 2) = 0 Then
                IsPrime = False: Exit Function
            End If
            i = i + 6
        Loop
        IsPrime = True
    End If
End Function