GO: проверьте, является ли число простым

Проверить, является ли число простым самым быстрым и эффективным способом, является тривиальной задачей для любого языка программирования. Go предлагает пакет math со встроенной функцией big для выполнения основных задач, но при этом эффективно.

Ints

Для целочисленных типов используйте ProbablyPrime(0) из пакета math/big. Этот тест на простоту дает 100% точность для входных данных меньше 264.

Пример кода:

const n = 1212121
if big.NewInt(n).ProbablyPrime(0) {
    fmt.Println(n, "is prime")
} else {
    fmt.Println(n, "is not prime")
}

Большие числа

Для большего количества необходимо предоставить желаемое количество тестов в ProbablyPrime (n). Для тестов n вероятность возврата истины для случайно выбранного непростого числа составляет не более (1/4) n. Обычный выбор - использовать n = 20; это дает количество ложных срабатываний 0,000,000,000,001.

z := new(big.Int)
fmt.Sscan("20828378347937489020982309820938029380947893749", z)
if z.ProbablyPrime(20) {
    fmt.Println(z, "is probably prime")
} else {
    fmt.Println(z, "is not prime")
}

Заявление об ограничении ответственности: в этом руководстве не учитывается оптимизация эффективности алгоритма

Если вы хотите поддержать мою работу, не стесняйтесь присылать чаевые:

$ BTC: 1EtMQNXADe5ZoSgbwox7Ug5TPvP8YWSpL3

$ QRL: Q010400e08175fe9823e6caa1aa3359686d7251a40eb432230d55f5b4e7388ec1c947b4361fb5cf