Улучшение пробного разделения теста на первичность

Question

Я узнаю о проверке чисел с простым числом, и мне интересно, как я могу сделать это быстрее для больших чисел (Как 2 ^ 64-1)

bool IsPrime(BigInteger number)
{
    if (number< 2) return false;
    else if (number< 4) return true;
    else if (number% 2 == 0) return false;
    else for (BigInteger u = 3; u*u <= Num; u += 2)
        if (number % u == 0) return false;
    return true;
}

Answer 1

Для очень незначительного улучшения, настолько незначительного, что вы его не заметите, вы можете сохранить одно if утверждение:

if (number < 2) return false;
else if (number % 2 == 0) return number == 2;
else for...

Для заметного улучшения я бы предложил использовать Сито Эратосфена вместо пробного деления.Если это все еще слишком медленно, то исследуйте другие методы, такие как Миллер-Рабин.

Даже с быстрыми методами, стоит использовать более медленные методы в течение короткого времени, скажем, пробуя все простые числа до 5000в качестве факторов, прежде чем приступить к задаче создания одного из более сложных тестов.Нет смысла проделывать большую работу, чтобы определить, что 4 327 856 799 435 являются составными.